摘要:基础数列求和题

luogu1593_因子和

题面

题目分析

这道题是要求$\sigma(a^b)$.

通过唯一分解定理,$a = p_{1}^{k_1} p_{2}^{k_2} \cdots p_{n}^{k_n}$,考虑因数根据质因数的组合方式,我们可以得到除数和函数的求法:

所以我们给$a$的每个质因数的幂次暴力乘上一个$b$,然后按照上式求积即可.

但是注意到模数是$9901$,这个数虽然是质数但是特别小,所以极有可能分母是这个数的倍数而导致不存在乘法逆元,也就是$a a^{-1}\equiv 1 \quad \bmod 9901$无解,事实上在$p = 59407 = 9901 \times 6 +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
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "iomanip"
#include "cmath"
#define R register
#define debug(x) printf("debug:%d\n",x)
const int big=10010,mod=9901;
int a,b,ans=1;
int p[big],k[big];
inline int read()
{
char c(getchar());
int x(0);
for(;!isdigit(c);c=getchar());
for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
return x;
}
inline int FastPow(int a,int b)
{
int sum(1);
for(;b;a=1ll*a*a%mod,b>>=1)(b&1)&&(sum=1ll*sum*a%mod);
return sum;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
#endif
a=read(),b=read();
if(b==0){printf("1\n");return 0;}
int len=sqrt(a);
for(R int i(2);i<=len;++i)
{
int x=i,y=a/i;
if(!(a%x))
{
p[++p[0]]=x;while(!(a%x)&&a>1)a/=x,++k[p[0]];
// if(x!=y){p[++p[0]]=y;while(!(a%y)&&a>1)a/=y,++k[p[0]];}
}
}
if(a>1)p[++p[0]]=a,k[p[0]]=1;
for(R int i(1);i<=p[0];++i)
if((p[i]-1)%mod)
{
int top=(FastPow(p[i],k[i]*b+1)-1+mod)%mod;
int botinv=FastPow(p[i]-1,mod-2);
ans=1ll*ans*(top*botinv%mod)%mod;
}
else
{
int sum(0),tmp(1);
for(R int j(1);j<=k[i]*b+1;tmp=tmp*p[i]%mod,++j)
sum=(sum+tmp)%mod;
ans=1ll*ans*sum%mod;
}
printf("%d\n",ans);
end:return 0;
}