时间限制: 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;
}