题目
题目描述
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).
输入
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.
样例输入
|
1 2 |
2 3 |
样例输出
|
1 2 |
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).
来源
Romania OI 2002
传送门
题解
问题分析
刚一看到这个题，一股浓浓的数论感就扑面而来，求A^B的约数和，暴力当然是不可取的，我们不妨换个角度
如果我们把A分解质因数，表示为
A=p_1^(c_1)_p_2^(c_2)_p_3^(c_3)_..._p_n^(c_n)
那么\( A^B \)可表示为
A=p_1^{(B_c_1)}_p_2^{(B_c_2)_p_3^(B_c_3)}_..._p_n^(B_c_n)
则\( A^B \)所有约数和为
(1+p_1+p_1^2+...+p_1^(B_c_1))_
质因数分解
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define MAXN 50001 const int MOD=9901; long long a,b; long long p[MAXN],c[MAXN]; long long m; long long ans; long long pow(long long p,long long n){ long long sq=1; while(n){ if(n&1)sq=(sq*p)%MOD; n>>=1; p=(p*p)%MOD; } return sq; } bool prime(int n){ if(n<2)return 0; for(int i=2;i<=sqrt(n);i++){ if(n%i==0)return 0; } return 1; } void divide(int n){ m=0; for(int i=2;i<=sqrt(n);i++){ if(n%i==0&&prime(i)){ p[++m]=i,c[m]=0; while(n%i==0)n/=i,c[m]++; } } if(n>1&&prime(n))p[++m]=n,c[m]=1; return; } long long sum(long long p,long long c){ if(c==0)return 1; if(c%2==0)return (sum(p,c/2-1)*(1+pow(p,c/2+1))+pow(p,c/2))%MOD; else return (sum(p,c/2)*(1+pow(p,c/2+1)))%MOD; } void work(){ ans=1; for(int i=1;i<=m;i++){ ans=(ans*sum(p[i],c[i]*b)%MOD)%MOD; } } int main(){ cin>>a>>b; divide(a); work(); printf("%lld",ans); return 0; } |