4 条题解
-
0
#include<bits/stdc++.h> using namespace std; int n; int prime[1000006],pct; bitset<1000006> not_prime; void euler(){ for(int i=2;i<=n;i++){ if(!not_prime[i]){ prime[++pct]=i; } for(int j=1;j<=pct&&prime[j]*i<=n;j++){ not_prime[i*prime[j]]=1; if(!(i%prime[j])) break; } } } const int P=1e9+7; long long ans=1; void find(){ for(int j=1;j<=pct;j++){ long long p=prime[j],ct=0; while(p<=n){ ct+=n/p;p=p*prime[j]; }ans=ans*(ct*2+1)%P; } } int main() { scanf("%d",&n); euler(); find(); printf("%lld",ans); return 0; } /* 1/x + 1/y = 1/n! 1/y = 1/n! - 1/x y = xn! / (x-n!) 若要让y为正整数, 需要: xn!和x-n!正整数 x-n! | xn! 设x-n! = k 则k|(k+n!)n!=kn!+n!*n! 因为k|kn!所以上式-> k|n!*n! 怎么求n!*n!的因数个数呢? 我们发现n!是由质数组成的 (这里先求n!的因数个数 只需要找到质数p在1~n中作为因数出现了多少次 (设为ct[p]次吧 cnt=连乘(ct[p_i]+1) //可以选p^0 ~ p^ct 那么对于n!*n!,只需让ct[p]*2即可 好的,那怎么找ct呢 在1~n中,ct[p] = n/p + n/p^2 +... (n/p记录了第一个p,n/p^2记录了第二个p...... OK*/
信息
- ID
- 208
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- (无)
- 递交数
- 25
- 已通过
- 15
- 上传者