「Luogu 5221」Product

发表于 | | 阅读次数:
字数统计: 753 字

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%