poj1845 Sumdiv 数学题
令人痛苦van分的数学题!
题意:求a^b的所有约数(包括1和它本身)之和%9901
这怎么做呀!!!
百度:约数和定理,会发现 p1^a1 * p2^a2 * ... * pn^an
这个数的约数和是:(1 + p1 + p1^2 + ... + p1^a1) * (1 + p2 + ... + p2^a2) * ... * (1 + pn + ... + pn^an)
证明:由乘法原理可直接证明
然后我们对于a^b
运用这个公式即可。
那么对于 (1 + pi + ... + pi^ai)
我们难道要暴力求吗?
不,这显然是个等比数列!我们用公式!
那么我们就成功WA了!
…查找原因,发现q-1
可能是9901
的整数倍,导致无法求逆元。
那么我们退而求次,用递归求和!
a1 + a1*q + a1*q^2 + ... + a1*q^n = (q^(n/2) + 1) * (a1 + a1*q + ... + a1*q^(n/2))
把上面那个式子分n的奇偶讨论一下就行了。
(法②:当q-1为9901的整数倍时,q % 9901 = 1,又因为a1 = 1,上式显然为n + 1)
然后我们开开心心的调了一年之后WA了….
查找原因:没开long long导致qpow爆了
然后就A了!
//poj1845 sumdiv
#include <cstdio>
using namespace std;
const int N = ,mo = ;
int p[N][],P;
int qpow(int a,int b) {
int ans=;
while(b) {
if(b&) {
ans=ans*a%mo;
}
a=a*a%mo;
b=b>>;
}
return ans;
} void split(int a,int b) {
for(int i=; a>; i++) {
if(!(a%i)) {
p[++P][] = i;
}
while(!(a%i)) {
a/=i;
p[P][]++;
}
}
for(int i=; i<=P; i++) {
p[i][]*=b;
}
return;
} long long getQsum(int a1,int q,int n) {
if(q==) {
return a1*n%mo;
}
if(n==) {
return a1;
}
if(n&) { //奇数
long long ans = ((+qpow(q,n>>))*getQsum(a1,q,n>>)+(a1*qpow(q,n-)))%mo;
return ans;
}
//偶数
long long ans = ((+qpow(q,n>>))*(getQsum(a1,q,n>>)))%mo;
return ans;
} void solve() {
long long ans=;
for(int i=; i<=P; i++) {
int temp=getQsum(,p[i][],p[i][]+);
ans*=temp;
ans%=mo;
}
printf("%I64d",ans);
return;
} int main() {
//freopen("in.in","r",stdin);
//freopen("my.out","w",stdout);
int a,b;
scanf("%d%d",&a,&b);
if(!a) {
printf("");
return ;
}
split(a,b);
solve();
return ;
}
AC代码:
我们学到了什么?
我们学到了什么?
- 约数和定理
- How to 求逆元
- How to 递归求等比数列和
- 开long long!!!!
————————end————————