By

文章目录
  1. 1. 题意
  2. 2. 分析

题意

给你A，B求$A^B$的所有因子的和模9901的值

分析

将A进行唯一分解，因为A在$5\times1e7$，所以A的质因子在$1e4$以内，我们预处理出$1e4$的素数表，然后对每个A计算其质因子的系数，又由生成函数可知，$A^B$的所有质因数的和为：$$sum=(1+p_1+p_1^1+p_1^2+p_1^3\dots+p_1^{a_1B})(1+p_2+p_2^1+p_2^2+p_2^3\dots+p_2^{a_2B})\dots(1+p_n+p_n^1+p_n^2+p_n^3\dots+p_n^{a_nB})$$
计算
$$\frac{p_1^{a_1B+1}-1}{p_1-1}$$
需要用到乘法逆元，并同时需要处理当$p_1-1$与9901不同余的时候的状况，而且其中因为快速幂的值可能过大，需要快速乘加速。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define MAXN 10007
#define MOD 9901
#define ll long long
using namespace std;
ll check[MAXN],prime[MAXN];
ll getprime(){
    ll tot=0;
    memset(check,false,sizeof(check));
    check[0]=check[1]=true;
    for(int i=2;i<MAXN;i++){
        if(!check[i]){
            prime[tot++]=i;
            for(int j=i<<1;j<MAXN;j+=i){
                check[j]=true;
            }
        }
    }
    return tot;
}
ll getprime_Euler(){
    ll tot=0;
    memset(check,false,sizeof(check));
    check[0]=check[1]=true;
    for(int i=2;i<MAXN;i++){
        if(!check[i]){
            prime[tot++]=i;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>MAXN){
                break;
            }
            check[i*prime[j]]=true;
            if(i%prime[j]==0){
                break;
            }
        }
    }
    return tot;
}
ll mul_mod(ll a,ll b,ll m){//wa:mul_mod写错了。。。
    ll ans=0;
    a%=m;
    while(b>0){
        if(b&1){
            ans+=a;
            ans%=m;
        }
        b=b>>1;
        a+=a;
        a%=m;
    }
    return ans;
}
ll pow_mod(ll a,ll b,ll m){
    ll ans=1;
    a%=m;
    while(b>0){
        if(b&1){
            ans=mul_mod(ans,a,m)%m;
        }
        b=b>>1;
        a=mul_mod(a,a,m)%m;
    }
    return ans;
}
int main()
{
    ll a,b,m,num,ans;
    ans=1;
    ll tot=getprime_Euler();
    scanf("%lld%lld",&a,&b);
    for(int i=0;prime[i]*prime[i]<=a;i++){
        if(a%prime[i]==0){
            num=0;
            while(a%prime[i]==0){
                num++;
                a/=prime[i];
            }
            if((prime[i]-1)%MOD==0){
                /* 如果此时prime[i]-1是素数9901的整数倍，假设a,则 (a-1) mod 9901 = 0
                a^0 + a^1 + a^2 + ... + a^n = 1 + ... + (a-1)^n + (a-1)^(n-1) + ... + (a-1)^0 = n + 1
                所以可以得出以下式子
                */
                ans=(ans*((num*b+1)%MOD))%MOD;
            }
            else{
                m=MOD*(prime[i]-1);
                //cout<<m<<endl;
                ans=ans*((pow_mod(prime[i],num*b+1,m)+m-1)/(prime[i]-1))%MOD;
            }
        }
    }
    if(a!=1){
        if((a-1)%MOD==0){
            ans=(ans*((b+1)%MOD)%MOD);
        }
        else{
            m=MOD*(a-1);
            //cout<<m<<endl;
            ans=ans*((pow_mod(a,b+1,m)+m-1)/(a-1))%MOD;
        }
    }
    printf("%lld\n",(ans+MOD)%MOD);
}
文章目录
  1. 1. 题意
  2. 2. 分析