poj1845 Sumdiv

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代码:

我们学到了什么?

我们学到了什么?

  1. 约数和定理
  2. How to 求逆元
  3. How to 递归求等比数列和
  4. 开long long!!!!

————————end————————

上一篇:第7章 使用寄存器点亮LED灯—零死角玩转STM32-F429系列


下一篇:Mybatis注解开发模糊查询