首先，我们知道，任意一个大于 (1) 的正整数 (a) 都可以表示为下面的形式（(prod) 是连乘符号，与 (sum) 类似）：
[a=prod_{i=1}^m p_i^{c_i}left(c_iinmathbb{Z^+}
ight)
]
其中 (p_i) 为互不相同的质数，满足 (p_1<p_2<cdots<p_m)，也就是 (a) 的质因数，(m) 为 (a) 的质因数个数。
这也就是小学奥数里学的质因数分解。
现在我们已经知道了 (a) 的质因数分解，那么 (a) 的因子和为：
[left(p_1^0+p_1^1+p_1^2+cdots+p_1^{c_1}
ight)left(p_2^0+p_2^1+p_2^2+cdots+p_2^{c_2}
ight)cdotsleft(p_m^0+p_m^1+p_m^2+cdots+p_m^{c_m}
ight)
]
也就是：
[prod_{i=1}^m sum_{j=0}^{c_i} p_i^j
]
接下来我们来讨论 (a^b) 的因子和。
根据初中所学知识 (forall s inmathbb Z,;(xy)^s=x^sy^s)，我们可以得出：
[egin{align*} a^b &=left(prod_{i=1}^m p_i^{c_i}
ight)^b\ &=prod_{i=1}^m p_i^{bc_i}end{align*}
]
它的因子和为：
[prod_{i=1}^m sum_{j=0}^{bc_i} p_i^j
]
上面一长串式子，如果暴力求的话，复杂度明显会爆炸。如果测评机是太湖之光当我没说
所以我们考虑优化它。
来看后面这个 (sum)，
不难观察出，这是一个等比数列。根据等比数列的求和公式，我们可以得出：
[sum_{j=0}^{bc_i} p_i^j=frac{p_i^{bc_i+1}-1}{p_i-1}
]
(p_i^{bc_i+1}-1) 可以用快速幂，因为这道题要取模，所以需要搞一下 (p_i-1) 的逆元。
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e7+10;
const int MOD=9901;
int qpow(int a,int n,int m)
{
int base=a%m,ans=1;
while(n)
{
if(n&1) ans=(ans*base)%m;
base=(base*base)%m;
n>>=1;
}
return ans;
}
int a[N],c[N],n,b,cnt=0;
void init()
{
int i=2;
while(n>1)
{
if(!(n%i))
{
n/=i;
a[++cnt]=i;
c[cnt]=1;
while(!(n%i))
{
n/=i;
c[cnt]++;
}
}
i++;
if(i*i>n) break;
}
if(n>1)
{
a[++cnt]=n;
c[cnt]++;
}
}
int inv(int s,int p) {return qpow(s,p-2,p);}
int main()
{
scanf("%d %d",&n,&b);
init();
int ans=1;
for(int i=1;i<=cnt;i++)
{
int z=c[i]*b+1;//指数
int in=inv(a[i]-1,MOD);//inv(a-1)
int s=(qpow(a[i],z,MOD)-1+MOD)%MOD;
s=(s*in)%MOD;
ans=(ans*s)%MOD;
}
printf("%d",ans);
}
然后你就得到了 88pts 的好成绩。
问题出在哪呢？
问题就在 (9901) 这个模数太小了，(p_i-1) 有可能是它的倍数，(p_i-1) 就没有关于 (9901) 的逆元。此时，就会出一些奇奇怪怪的锅，比如逆元搞出来 (0) 什么的，所以我们需要对这种情况进行特判。
不难得出，当 (p_i-1mod 9901=0) 时，(p_imod 9901=1)。
此时，我们可以推算出：
[egin{align*}left(sum_{j=0}^{bc_i} p_i^j
ight)mod 9901 &=left(sum_{j=0}^{bc_i} left(p_i^jmod 9901
ight)
ight)mod 9901\&=left(sum_{j=0}^{bc_i} 1
ight)mod 9901\&=left(bc_i+1
ight)mod 9901end{align*}
]
在特判的时候把 (left(bc_i+1 ight)mod 9901) 搞进去就可以啦。
AC code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e7+10;
const int MOD=9901;
int qpow(int a,int n,int m)
{
int base=a%m,ans=1;
while(n)
{
if(n&1) ans=(ans*base)%m;
base=(base*base)%m;
n>>=1;
}
return ans;
}
int a[N],c[N],n,b,cnt=0;
void init()
{
int i=2;
while(n>1)
{
if(!(n%i))
{
n/=i;
a[++cnt]=i;
c[cnt]=1;
while(!(n%i))
{
n/=i;
c[cnt]++;
}
}
i++;
if(i*i>n) break;
}
if(n>1)
{
a[++cnt]=n;
c[cnt]++;
}
}
int inv(int s,int p) {return qpow(s,p-2,p);}
int main()
{
scanf("%d %d",&n,&b);
init();
int ans=1;
for(int i=1;i<=cnt;i++)
{
if((a[i]-1)%MOD)
{
int z=c[i]*b+1;//指数
int in=inv(a[i]-1,MOD);//inv(a-1)
int s=(qpow(a[i],z,MOD)-1+MOD)%MOD;
s=(s*in)%MOD;
ans=(ans*s)%MOD;
}
else ans=ans*(b%MOD*c[i]+1)%MOD;
}
printf("%d",ans);
}
测评信息：
:Implementing a Membership Provider