$\text{Description}$
给定正整数 $n,p$，求
$n\le 10^{10},5\times 10^8\le p\le 1.1\times 10^9$。
$\text{Solution}$
欧拉反演：
交换求和次序：
背后那一坨可以 $O(1)$ 算出，所以问题变为计算 $f(n)=\varphi(n)n^2$ 的前缀和。
那我们知道 $\varphi(n)$ 的前缀和就是卷上一个 $\operatorname{1}$ 变成 $\operatorname{Id}$ 就可以杜教筛算了。
后面这个 $n^2$ 怎么算？
你看狄利克雷卷积的过程中是一个 $d$ 和一个 $n/d$ 相乘，它们直接就成常数了。
那么肯定选择 $g(n)=n^2$，我们知道 $g$ 的前缀和可以 $O(1)$ 算，那么还有：
也可以 $O(1)$ 算前缀和。
杜教筛跑一下就出来了。
$\text{Code}$
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
| #include<bits/stdc++.h>
#define REG register
using namespace std;
const int N=5e6;
typedef long long ll;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int p;
ll n;
int _2,_6;
inline int Pow(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%p;
a=1ll*a*a%p,b>>=1;
}
return res;
}
inline int _(ll n){n%=p;return (int)(n*(n+1)%p*_2%p);}
inline int __(ll n){n%=p;return (int)(n*(n+1)%p*(2*n%p+1)%p*_6%p);}
inline int ___(ll n){int t=_(n%p);return (int)(1ll*t*t%p);}
int Phi[N+10],Prm[N+10],vis[N+10],cnt;
inline void Euler(){
Phi[1]=1,_2=Pow(2,p-2),_6=Pow(6,p-2);
for(REG int i=2;i<=N;++i){
if(!vis[i]) Phi[i]=i-1,Prm[++cnt]=i;
for(REG int j=1;j<=cnt&&i*Prm[j]<=N;++j){
vis[i*Prm[j]]=1;
if(i%Prm[j]==0){Phi[i*Prm[j]]=1ll*Phi[i]*Prm[j]%p;break;}
Phi[i*Prm[j]]=1ll*Phi[i]*(Prm[j]-1)%p;
}
}
for(REG int i=2;i<=N;++i) Phi[i]=(1ll*i*i%p*Phi[i]%p+Phi[i-1])%p;
}
map<ll,int> SPhi;
inline int Seive(ll n){
if(n<=N) return Phi[n];
if(SPhi.find(n)!=SPhi.end()) return SPhi[n];
int res=0;ll l=2,r=0;
for(;l<=n;l=r+1)
r=n/(n/l),res=(res+1ll*Seive(n/l)*((__(r)-__(l-1)+p)%p)%p)%p;
res=(___(n)-res+p)%p;
return SPhi[n]=res;
}
inline void Work(){
read(p),read(n),Euler();
int res=0;
ll l=1,r=0;
for(;l<=n;l=r+1)
r=n/(n/l),res=(res+1ll*___(n/l)*((Seive(r)-Seive(l-1)+p)%p)%p)%p;
printf("%d\n",res);
}
int main(){Work();}
|
