撰写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
Note:
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进行质因数分解+多项式表示所有约数和+分治得到等比数列和+快速幂
代码：
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
const int maxn=10;
int fac[10000];
int fre[10000];
const int mode=9901;
int work_quality_factor(int n)
{
int res,temp,i;
res=0;
temp=n;
for(i=2;i*i<=temp;i++)
if(temp%i==0)
{
fac[res]=i;
fre[res]=0;
while(temp%i==0)
{
temp=temp/i;
fre[res]++;
}
res++;
}
if(temp>1)
{
fac[res]=temp;
fre[res++]=1;
}
return res;
}
long long Mode(long long a, long long b)
{
long long sum = 1;
while (b) {
if (b & 1) {
sum = (sum * a) % mode;
b--;
}
b /= 2;
a = a * a % mode;
}
return sum;
}
ll sum(int p,int c){
if(p==0)return 0;
if(c==0)return 1;
if(c&1){
return (1+Mode(p,c/2+1))%mode*sum(p,c/2)%mode;
}else{
return (1+Mode(p,c/2+1) )%mode*sum(p,c/2-1)%mode+Mode(p,c/2)%mode;
}
}
int main(){
int a,b;
cin>>a>>b;
int res=work_quality_factor(a);
rep(i,0,res-1){
fre[i]*=b;
}
ll SUM=1;
rep(i,0,res-1){
SUM=SUM*sum(fac[i],fre[i])%mode;
}
cout<<SUM;
return 0;
}