弹药科技

时间限制: 1 Sec 内存限制: 128 MB

题目描述

经过精灵族全力抵挡，精灵终于坚持到了联络系统的重建，于是精灵向人类求助，

大魔法师伊扎洛决定弓}用博士的最新科技来抗敌。 伊扎洛:“博士，还没好吗?” 博士:“只差一步了!只需要在正确的位置装上弹药就可以了!”博士的最新科技是全新的炸弹，但是现在还需要一步装弹药的操作。博士的炸弹有N!个位置可以装弹药(>.<)，但是只有在正确的位置装上弹药才能启动，博士将装弹药的位置编号为1到N!，一个位置i需要装弹药，当且仅当gcd(i, N!) ≠ 1且 N! mod i ≠0，现在博士不要求你求出所有装弹药位置，只需要你求出满足要求 的位置的数量就可以了。

输入 一个数N

输出

表示满足要求的位置数量，答案对mod1000000007输出

样例输入

4

样例输出

9

提示 【数据范围】

N <= 1000000

N!为总方案数。那么题目要求的答案便是总方案数n!减去与n!互质的数与n!的所有因子。

与n！互质的数容易想到使用欧拉函数来求

\(\varphi(n)=n*\frac{p_{1}}{(p_{1}-1)}*\frac{p_{2}}{(p_{2}-1)}*...*\frac{p_{n}}{p_{n}-1})\)

其中\(p_{i}\)表示把n分解成质因数的结果。

n！的因数个数也可以这么求\((w_{1}+1)*(w_{2}+1)*...*(w_{n}+1)\)

w为唯一分解后质数的指数。

需要注意的是，w不能直接求，需要用Lengendre定理。（这里Lengendre定理不能求模）

#include<iostream>

#include<cstdio>

using namespace std;

#define N 1000010

#define MOD 1000000007

#define LL long long

LL idx[N],prime[N],n,cnt,phi,fac=1,sum=1;

bool vis[N];

void Euler(int n) {

    for(int i=2;i<=n;i++) {

        if(vis[i]==0)

            prime[++cnt]=i;

        for(int j=1;j<=cnt && 1ll*i*prime[j]<=n;j++) {

            vis[i*prime[j]]=1;

            if(i%prime[j]==0) break;

        }

    }

}

LL LG(LL n,LL P) {

    LL ans=0,sum=P;

    while(n>=sum) {

        ans=(ans+n/sum);

        sum=sum*P;

    }

    return ans;

}

LL qkpow(LL base,LL indexx)

{

    LL fuck=1;

    while(indexx>0)

    {

        if(indexx&1)

            fuck=fuck*base%MOD;

        base=base*base%MOD;

        indexx>>=1;

    }

    return fuck%MOD;

}

LL inv(LL sum) {

    return qkpow(sum,MOD-2);

}

int main() {

    cin>>n;

    Euler(n);

    for(int i=1;i<=n;i++)

        fac=(1ll*fac*i)%MOD;

    phi=fac;

    for(int i=1;i<=cnt;i++) {

        phi=1ll*phi*(prime[i] - 1)%MOD*inv(prime[i]) %MOD;

        sum=(1ll*sum*(LG(n,prime[i])+1)%MOD)%MOD;

    }

    cout<<(fac-phi+MOD+MOD-sum+1)%MOD;

}