實驗吧 大數模運算 -开发者知识库

實驗吧 大數模運算 -开发者知识库,第1张

實驗吧 大數模運算

題目鏈接:http://www.shiyanbar.com/ctf/1906

題目大意:求$12345^{12345}$的所有約數之和,並對其取模$9901$再輸出。

唯一分解定理 生成函數

對於任意一個數$a$,由唯一分解定理得$a=\prod_{i=0}^k p_i^{c_i}$,

故由生成函數的定義可知,其約數之和為$S=\prod_{i=0}^k (\sum_{j=0}^{c_i} p_i^j)$.

而對於$a^n$,則有$a=\prod_{i=0}^k p_i^{n \times c_i}$.

故其約數之和為$S'=\prod_{i=0}^k (\sum_{j=0}^{n \times c_i} p_i^j)$.

由等比數列求和公式即可求得答案.

代碼如下:

 1 #include <cstdio>
 2 #define N 10005
 3 using namespace std;
 4 typedef long long ll;
 5 ll a=12345,n=12345,m=9901,p[N],c[N],k,ans=1;
 6 ll minus(ll a,ll b){return (a-b m)%m;}
 7 ll mul(ll a,ll b){return (a*b)%m;}
 8 ll powmod(ll a,ll n){
 9     ll r=1;
10     while(n){
11         if(n&1)r=mul(r,a);
12         a=mul(a,a);
13         n>>=1;
14     }return r;
15 }
16 int main(void){
17     for(int i=2;i*i<=a;  i)if(a%i==0){
18         while(a%i==0){
19             c[k] =n;
20             a/=i;
21         }p[k  ]=i;
22     }
23     if(m!=1){
24         c[k] =n;
25         p[k  ]=a;
26     }
27     for(int i=0;i<k;  i)
28         ans=mul(ans,mul(minus(powmod(p[i],c[i] 1),1),powmod(p[i]-1,m-2)));
29     printf("%lld\n",ans);
30 }

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复