POJ 1845-Sumdiv（厉害了这个题）
Description
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901). Input
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks. Output
The only line of the output will contain S modulo 9901. Sample Input
2 3 Sample Output
15 Hint
2^3 = 8. The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 15 modulo 9901 is 15 (that should be output).
题意很简单a的b次方的因数和对9901取模； 这个题题意很简单，但是看数据量加操作肯定超时，涵盖知识量极多。 1.快速幂：递归求解指数运算。 指数过大无法运算，虽然不知道他们是怎么做的，估计跟这个差不多。 PS
typedef long long LL;
LL power(int a,int b){
LL ans=1;
while(b){
if(p&1) ans=ans*a; /判断是否为奇数（可以%2，按位或&可能快一点）
a=a*a;
b>>=1;
}
return ans;以2 ^ 8 和2 ^ 9为例， a=2,b=8; b是偶数，进行下一步 a=22=4; b=4; b是偶数，进行下一步 a=44=16: b=2; next a=1616=256 b=1; next b是奇数； ans=1a=256； 只用了log2n次的乘法； 2.A^B的所有约数之和为： sum = [1+p1+p12+…+p1 (a1*B)] * [1+p2+p22+…+p2(a2*B)] … [1+pn+pn2+…+pn(an*B)]. 3.埃氏筛法 直接板子（这里我用了近似的思想，当时还没明白这个方法）
int a[maxx];
int b[maxx+1];
int gg(int n)
{
int p=0;//记录素数个数
for(int i=0;i<n+1;i++)b[i]=1;
b[0]=0;
b[1]=0;
//准备完毕
for(int i=2;i<=n;i++){
if(b[i]){
a[p++]=i;//记录素数和个数
for(int j=2*i;j<=n;j+=i)b[j]=0;//剔除倍数
}
}
return p;//返回素数个数
}#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#define MOD 9901
using namespace std;
int a,b,z;
int p[10000]; //质数
int p_n[10000];//质数个数
void Zhi()//质数打表，求小于根号a的质数
{
int t = a;
for (int i=2; i*i<=a; i++)//开方运算比乘法用时间长
{
if (t%i==0)
{
p[z]=i;
p_n[z]=1;
t/=i;
while (t%i==0)
{
p_n[z]++;
t/=i;
}
z++;
}
if (t==1) break;
if (i!=2)
i++;//2.3.5.7.9...
}
if (t!=1)//本身就是质数
{
p[z]=t;
p_n[z]=1;
z++;
}
}
int Mi(int a, int b)//快速幂
{
int res = 1;
a%=MOD;
while(b)
{
if (b&1) res = (res * a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
int Ys(int p , int n)//递归求等比系数
{
if (n==0) return 1;
if (n%2==1)
return ((Mi(p,n/2+1)+1) * Ys(p,n/2))%MOD;
else
return ((1+Mi(p,n/2+1)) * Ys(p,n/2-1) + Mi(p,n/2))%MOD;
}
int main()
{
while (scanf("%d%d",&a,&b)!=EOF)
{
z=0;//质数个数
Zhi();
int ans = 1;
for (int i=0; i<z; i++)
{
ans=(ans*Ys(p[i],p_n[i]*b))%MOD;
}
printf("%d\n",ans);
}
return 0;
}