Divisors of the Divisors of An Integer 2019-09-22 算法竞赛 暂无评论 84 次阅读 # Divisors of the Divisors of An Integer 链接：[http://codeforces.com/gym/102040](http://codeforces.com/gym/102040)  时限：3000ms 空间：1024MB ## 题意： d(n) 是n 的约数个数 sndd(n) 是n 约数的约数个数 题目给了个n，要求sndd( n! ) ## 思路： 质因数分解；若一个数 k=p1 ^ c1 * p2 ^ c2 * p3 ^ c3 + ...... 其约数个数为 (1+c1) * (1+c2) * (1+c3)*... *假设n!=p1 ^ c1 * p2 ^ c2 * p3 ^ c3 + ...... 则任意一个数 m=p1 ^ a1 * p2 ^ a2 * p3 ^ a3 + ...... ( 0<=a1<=c1 , 0<=a2<=c2,0<=a3<=c3,......) 均为 n! 的约数 所以sndd(n!) = $\sum_{a1=0,a2=0,a3=0,...}^{c1,c2,c3,...}$(1+ a1) * (1+a2) * (1+a3) *... 合并化简一下（或者从考虑每个ai 的贡献看） sndd(n!) = $\prod$ $\frac{(1+ci ) \times (2+ci ) }{ 2}$ ## 代码： ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; const int Mod=1e7+7; int prime[N]; bool is_prime[N]; ll Ans,c; void sieve(int n) { int p=0; for(int i=0; i<=n; i++) { is_prime[i]=true; } is_prime[0]=is_prime[1]=false; for(int i=1; i<=n; i++) { if(is_prime[i]) { prime[p++]=i; for(int j=i*2; j<=n; j+=i) { is_prime[j]=false; } } } } ll get(int n, int p) { ll s = 0; while (n) s += n / p, n /= p; return s; } int main() { sieve(1000005); int n; while(~scanf("%d",&n)&&n) { Ans=1; for(int i=0; prime[i]<=n; i++) { c=get(n,prime[i]); Ans=( ((1+c)*(2+c)/2)%Mod )*Ans%Mod; } printf("%I64d\n",Ans); } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭