[poj1845]sumdiv 题解

部分思路来源：李煜东dalao的《算法竞赛进阶指南》

我真推不出算数基本定理的推论
好书啊

solve

• 由算数基本定理得到：
  • 
  • LZYXT的图
  • 对于爻乘B方，向右扩展到B*c_i即可（详细见书）
• 然后枚举质因数和其指数，用快速幂算即可，然后套公式
• 爻特判的喵~
• （有时间再写得详细一点）

Code

#include<bits/stdc++.h>
#define mo 9901
using namespace std;
const int maxn=3e6+10;
long long a,b;
long long prime[maxn];
bool is_no_p[maxn]={1,1};
long long k[maxn],m[maxn],tot;
void Prime(long long n)
{for (long long i=2;i<=n;i++){if (!is_no_p[i]) prime[++prime[0]]=i;for (long long j=1;j<=prime[0] && i*prime[j]<=n;j++){is_no_p[i*prime[j]]=1;if (i%prime[j] == 0) break;}}
}
void func()
{for (long long i=2;i<=prime[0];i++){if (a%i == 0){k[++tot]=i;long long cnt=0;while(a%i == 0){cnt++;a/=i;}m[tot]=cnt*b;}}if (a>1){k[++tot]=a;m[tot]=b;}
}
long long ksm(long long x,long long y)
{long long cnt=1;while(y){if (y&1) cnt=(cnt*x)%mo;x=(x*x)%mo;y>>=1;}return cnt;
}
int main()
{cin >> a >> b;if (a == 0){cout << 0 << endl;return 0;}Prime(a);func();long long ans=1;for (long long i=1;i<=tot;i++){long long p=0;for (long long j=0;j<=m[i];j++){p=(p+ksm(k[i],j))%mo;}ans=(ans*p)%mo;}cout << ans << endl;return 0;
}