「Luogu 5221」Product

Description

题目链接:Luogu 5221

求下列式子的值(对 $104857601​$ 取模):

数据范围:$1\le n\le 10^6$


Solution

我们先拆一下式子:

发现分子可以直接计算,接下来只考虑分母:

第二个指数和「SDOI 2008」仪仗队 很像,即为:

我们预处理 $\varphi$ 的前缀和然后直接做就可以了。

注意:指数上的值对 $\varphi(\text{mod})$ 取模。本题卡空间,请尽量优化空间复杂度防止 $\text{MLE}$。

时间复杂度:$O(n+n\log n)$(可以通过数论分块优化到 $O(n+\sqrt n\log n)$)


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
#include <cstdio>

const int N=1e6+5;
const int mod=104857601;
int n,tot,p[N/10],phi[N];
bool flg[N];

void sieve(int n) {
phi[1]=1;
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
} else {
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
for(int i=1;i<=n;++i) (phi[i]+=phi[i-1])%=(mod-1);
}
int pow(int x,int p) {
int ans=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ans=1LL*ans*x%mod;
return ans;
}
int calc1(int n) {
int ans=1;
for(int i=1;i<=n;++i) ans=1LL*ans*pow(i,2*n)%mod;
return ans;
}
int calc2(int n) {
int ans=1;
for(int i=1;i<=n;++i) {
int cnt=2*phi[n/i]-1+mod-1;
ans=1LL*ans*pow(i,2LL*cnt%(mod-1))%mod;
}
return ans;
}
int main() {
scanf("%d",&n);
sieve(n);
printf("%lld\n",1LL*calc1(n)*pow(calc2(n),mod-2)%mod);
return 0;
}

数论分块优化后:

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
#include <cstdio>

const int N=1e6+5;
const int mod=104857601;
int n,tot,p[N/10],phi[N];
bool flg[N];

int pow(int x,int p) {
int ans=1;
for(;p;p>>=1,x=1LL*x*x%mod) if(p&1) ans=1LL*ans*x%mod;
return ans;
}
int inv(int x) {
return pow(x,mod-2);
}
void sieve(int n) {
phi[1]=1;
for(int i=2;i<=n;++i) {
if(!flg[i]) p[++tot]=i,phi[i]=i-1;
for(int j=1;j<=tot&&i*p[j]<=n;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
} else {
phi[i*p[j]]=phi[i]*phi[p[j]];
}
}
}
for(int i=1;i<=n;++i) (phi[i]+=phi[i-1])%=(mod-1);
}
int calc1(int n) {
int ans=1;
for(int i=1;i<=n;++i) ans=1LL*ans*i%mod;
return pow(ans,2*n);
}
int calc2(int n) {
int ans=1,p1=1,f1=1,p2=1,f2=1;
for(int i=1,j;i<=n;i=j+1) {
j=n/(n/i);
while(p1<=j) f1=1LL*f1*p1++%mod;
while(p2<i) f2=1LL*f2*p2++%mod;
int cnt=2*phi[n/i]-1+mod-1;
ans=1LL*ans*pow(1LL*f1*inv(f2)%mod,2LL*cnt%(mod-1))%mod;
}
return ans;
}
int main() {
scanf("%d",&n);
sieve(n);
printf("%lld\n",1LL*calc1(n)*inv(calc2(n))%mod);
return 0;
}
0%