当前位置 博文首页 > Kuricip的博客：Sumdiv（同余模运算、素因子分解、递归二分求等
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^BA
B. Determine S modulo 9901 (the rest of the division of S by 9901).
The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.
The only line of the output will contain S modulo 9901.
2 3
15
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 = p1^k1 * p2^k2 * … * pn^kn;
A^B = p1^(k1* B) * p2^(k2* B) … pn^(kn* B);
二：同余模定理
(a+b)%m=(a%m+b%m)%m
(ab)%m=(a%mb%m)%m
三：一个数用素因子乘积表示后其约数和公式,
sum = [1+p1+p1^2 +…+p1^(k1* B)] * [1+p2+p2^2+ … +p2^(k2* B)] * … * [1+pn+pn^2+ …+pn^(kn*B)].
四：用递归二分求等比数列1+pi+pi^2 + pi^3+ … +pi^n：
(1).n为奇数，(1 + p + p^2 +…+ p^(n/2)) * (1 + p^(n/2+1))；
(2).n为偶数，(1 + p + p^2 +…+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2);
五：快速幂求q^n；
六：分解A：
A对每个素数不断取模（例如2，A%2==0时 ，2出现的次数++，A/=2)；
当A%2!=0时，则A对下一个素数3不断取模…
以此类推，直到A=1时；
注意特判(当经过素因子分解后，A!=1)，也就是A本身就是素数时，无法被其他素数分解，意味着自己就是其本身的素数分解式。
#include <iostream>
using namespace std;
const int mod = 9901;
const int MAXN=10000;
typedef long long ll;
ll quick_pow(ll a, ll b) //快速幂
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll sum(ll p, ll n){
if(n==0)
return 1;
if(n%2) //n为奇数
return (sum(p,n/2)*(1+quick_pow(p,n/2+1)))%mod;
else //n为偶数
return (sum(p,n/2-1)*(1+quick_pow(p,n/2+1))+quick_pow(p,n/2))%mod;
}
int main(){
int A, B, k=0;
int p[MAXN], n[MAXN]; //p为底数，n为指数
cin>>A>>B;
for(int i=2; i*i<=A; ){ //素因子分解
if(A%i==0){ //i为A的因式
p[k]=i; //记录底数
n[k]=0;
while(!(A%i)){
n[k]++; //记录指数
A/=i;
}
k++;
}
if(i==2) //更快遍历（也可以提前素数打表
i++;
else
i+=2;
}
if(A!=1){ //特判A为质数
p[k]=A;
n[k++]=1;
}
ll ans=1;
for(int i=0; i<k; i++)
ans=(ans*(sum(p[i], n[i]*B)%mod))%mod;
cout<<ans<<endl;
return 0;
}
