首页 > 代码库 > poj 1845 数论综合
poj 1845 数论综合
题意：求A^B的所有因数的和 mod 9901
sol：一开始毫无思路，因为很多定理都不知道-_-||
1. 整数的唯一分解定理：
任意正整数都有且只有一种方式写出其素因子的乘积表达式。
A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn) 其中pi均为素数
2. 约数和公式：
对于已经分解的整数A=(p1^k1)*(p2^k2)*(p3^k3)*....*(pn^kn)
有A的所有因子之和为
S = (1+p1+p1^2+p1^3+...p1^k1) * (1+p2+p2^2+p2^3+….p2^k2) * (1+p3+ p3^3+…+ p3^k3) * .... * (1+pn+pn^2+pn^3+...pn^kn)
熟悉了公式定理就好办了。
首先求出p[i]、k[i]
然后就有
A=p1^n1*p2^n2*......*pk^nk
A^B=(p1^(B*n1))*(p2^(b*n2))*......*(pk^(b*nk))
然后求出S即可。
注意：一开始我用等比数列求和公式求S，还用了pow_mod。其实这样不行。
比如数据59407 1，
59407 mod 9901=1，最终得出的结果成了0
模运算也不是随便用的，还得按公式来= =
Reference：http://blog.csdn.net/lyy289065406/article/details/6648539
1 #include "iostream" 2 #include "cstdio" 3 using namespace std; 4 #define P 9901 5 #define LL __int64 6 LL n[1000],p[1000]; //A=**(p[i]^n[i]) 7 LL k,A,B; 8 9 LL pow_mod(LL p, LL k,int mod) //(p^k)%mod10 {11 LL ans = 1;12 while(k) {13 if (k & 1) ans = ans * p % mod;14 p = (LL)p*p % mod;15 k >>= 1;16 }17 return ans;18 }19 20 void divide()21 {22 k=1;23 /*常规做法：分解整数A (A为非质数)*/24 for(int i=2; i*i<=A;) //根号法+递归法25 {26 if(A%i==0)27 {28 p[k]=i;29 n[k]=0;30 while(!(A%i))31 {32 n[k]++;33 A/=i;34 }35 k++;36 }37 if(i==2) //奇偶法38 i++;39 else40 i+=2;41 }42 /*特殊判定：分解整数A (A为质数)*/43 if(A!=1)44 {45 p[k]=A;46 n[k++]=1;47 }48 k--;49 }50 51 LL calc(LL p,LL n) //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod52 { //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))53 if(n==0) //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)54 return 1;55 if(n%2) //n为奇数,56 return (calc(p,n/2)*(1+pow_mod(p,n/2+1,P)))%P;57 else //n为偶数58 return (calc(p,n/2-1)*(1+pow_mod(p,n/2+1,P))+pow_mod(p,n/2,P))%P;59 }60 61 int main()62 {63 //freopen("in.txt","r",stdin);64 while (cin>>A>>B)65 {66 divide();67 LL sum=1;68 for (LL i=1;i<=k;i++)69 {70 LL tm=calc(p[i],B*n[i]);71 sum=(sum*tm)%P;72 }73 cout<<sum<<endl;74 }75 return 0;76 }
poj 1845 数论综合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。