例题 POJ845
M - Sumdiv
求A^B的约数之和对mod取模
需要素数筛选和合数分解的程序，需要先调用getPrime（）；
为什么呢？
好我们来解决这个疑问。
先引入一个定理
算术基本定理：
任何一个大于 1 的自然数可以分解成一些素数的乘积；并且在不计次序的情况下，这种分解方式是唯一的（这个很重要）来自百度百科，
算术基本定理（别称唯一分解定理）
我们可以做一个简单的理解：
根据定理我们可以知道一个数n肯定能被分解成 n=p1^a1 * p2^a2 . . .*pn^an；
而一个数要么是由合数要么是质数构成的，合数又可以分解成质数和合数，那么我们继续想下去，最后就会发现都只是剩下质数的乘积。
举个栗子： 简单理解一下
18 可以由 2*9 或者说 3*6
然后 可以是2*3*3 或者 3*2*3
那么最后必然是： 2^1*3^2；
所以说，最后还是会化成了质数相乘的形式
证明这个定理我就不证明了（有点懒~
那么我们对于这道题，我们第一步需要做的是求出n（a^b）的所有素数因子，对于这个我们只要用素数筛，筛选出素数就可以了；
这里我用的是kuaingbin的模板：
const int MM=10000+1;
int prime[MM+1];
const int mod=9901;
void getprime()
{
memset(prime,0,sizeof(prime));
for(int i=2; i<=MM; i++)
{
if(!prime[i])
prime[++prime[0]]=i;
for(int j=1; j<=prime[0]&&prime[j]<=MM/i; j++)
{
prime[prime[j]*i]=i;
if(i%prime[j]==0)
break;
}
}
}
ll factor[100][2];
ll fatcnt;
int getFactors(ll x)
{
fatcnt=0;
ll tmp=x;
for(int i=1; prime[i]<=tmp/prime[i]; i++)
{
factor[fatcnt][1]=0;
if(tmp%prime[i]==0)
{
factor[fatcnt][0]=prime[i];
while(tmp%prime[i]==0)
{
factor[fatcnt][1]++;
tmp/=prime[i];
}
fatcnt++;
}
}
if(tmp!=1)
{
factor[fatcnt][0]=tmp;
factor[fatcnt++][1]=1;
}
return fatcnt;
}
第二步：按我们筛选出看所有的素数因子
那么接下来就要求出所有的因子之和。也就是
//计算1+p+p2`+`…+pn;//p为素数
//对于乘方时我们用快速幂，然后求和
ll pow_m(ll a,ll n)
{
ll ret=1;
ll tmp=a%mod;
while(n)
{
if(n&1)
ret=(ret*tmp)%mod;
tmp=tmp*tmp%mod;
n>>=1;
}
return ret;
}
//计算1+p+p^2+.....+p^n;
ll sum(ll p, ll n)
{
if(p==0)
return 0;
if(n==0)
return 1;
if(n&1)
{
return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
}
else return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2-1)+pow_m(p,n/2)%mod)%mod;
}
//返回A^B的约数之和%mod
ll solve(ll A,ll B)
{
getFactors(A);
ll ans=1;
for(int i=0; i<fatcnt; i++)
{
ans*=sum(factor[i][0],B*factor[i][1])%mod;
ans%=mod;
}
return ans;
}
所以也就 这样就解决这题了；
AC代码
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
using namespace std;
#define ll long long
const int MM=10000+1;
int prime[MM+1];
const int mod=9901;
void getprime()//kuaingbin的模板 素数筛选
{
memset(prime,0,sizeof(prime));
for(int i=2; i<=MM; i++)
{
if(!prime[i])
prime[++prime[0]]=i;
for(int j=1; j<=prime[0]&&prime[j]<=MM/i; j++)
{
prime[prime[j]*i]=i;
if(i%prime[j]==0)
break;
}
}
}
ll factor[100][2];
ll fatcnt;
int getFactors(ll x)//素数筛选和合数分解的程序
{
fatcnt=0;
ll tmp=x;
for(int i=1; prime[i]<=tmp/prime[i]; i++)
{
factor[fatcnt][1]=0;
if(tmp%prime[i]==0)
{
factor[fatcnt][0]=prime[i];
while(tmp%prime[i]==0)
{
factor[fatcnt][1]++;
tmp/=prime[i];
}
fatcnt++;
}
}
if(tmp!=1)
{
factor[fatcnt][0]=tmp;
factor[fatcnt++][1]=1;
}
return fatcnt;
}
//快速幂取余//
ll pow_m(ll a,ll n)
{
ll ret=1;
ll tmp=a%mod;
while(n)
{
if(n&1)
ret=(ret*tmp)%mod;
tmp=tmp*tmp%mod;
n>>=1;
}
return ret;
}
计算1+p+p^2+…+p^n;//求和
ll sum(ll p, ll n)
{
if(p==0)
return 0;
if(n==0)
return 1;
if(n&1)
{
return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
}
else return ((1+pow_m(p,n/2+1))%mod*sum(p,n/2-1)+pow_m(p,n/2)%mod)%mod;
}
//求A^B的约数之和对mod取模
//需要素数筛选和合数分解的程序，需要先调用getPrime（）；
ll solve(ll A,ll B)
{
getFactors(A);
ll ans=1;
for(int i=0; i<fatcnt; i++)
{
ans*=sum(factor[i][0],B*factor[i][1])%mod;
ans%=mod;
}
return ans;
}
int main()
{
int A,B;
scanf("%d %d",&A,&B);
getprime();//调用
printf("%d",solve(A,B));
return 0;
}
京公网安备 11010502036488号