Project Euler 754

发表于 更新于 分类于 阅读次数： 本文字数： 706 阅读时长 ≈ 1 分钟

Project Euler 754

题目

Product of Gauss Factorials

The Gauss Factorial of a number \(n\) is defined as the product of all positive numbers \(\leq n\) that are relatively prime to \(n\). For example \(g(10)=1\times 3\times 7\times 9 = 189\). Also we define \[\displaystyle G(n) = \prod_{i=1}^{n}g(i)\] You are given \(G(10) = 23044331520000\).

Find \(G(10^8)\). Give your answer modulo \(1\,000\,000\,007\).

解决方案

令函数\(f(N,n)\)表示在\(n< i\le N\)这些数中，有多少个\(i\)满足\(\gcd(n,i)=1.\)那么\(G(N)\)就可以写成：

\[G(N)=\prod_{n=2}^N n^{f(N,n)}\]

其中，通过容斥原理和莫比乌斯函数\(\mu\)的性质，不难写出

\[f(N,n)=\sum_{d\mid n}\mu(d)\left(\left\lfloor\dfrac{N}{d}\right\rfloor-\left\lfloor\dfrac{n}{d}\right\rfloor\right)\]

注意式子后面第二项是减去\(n\)以内的数。

最终直接进行计算即可，时间复杂度为\(O(N\log N)\)。

代码

本代码运行超过\(1\)分钟（约\(70\)秒），我暂时没有比较好的思路来优化这道题。

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
# include <bits/stdc++.h>
using namespace std;
const int N=1e8;
int mod=1000000007;
int qpow(int n,int m){
    int ans=1;
    for(;m;m>>=1){
        if(m&1) ans=1ll*ans*n%mod;
        n=1ll*n*n%mod;
    }
    return ans;
}
char mu[N+1];
bool vis[N+1];
int f[N+1];
int pr[N/10+100],m=0;
int main(){
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!vis[i]){
            pr[++m]=i;
            vis[i]=1;mu[i]=-1;
        }
        for(int j=1;j<=m;j++){
            if(pr[j]>N/i) break;
            vis[i*pr[j]]=1;
            if(i%pr[j]) mu[i*pr[j]]=-mu[i];
            else{
                mu[i*pr[j]]=0;break;
            }
        }
    }
    for(int d=1;d<N;d++){
        if(mu[d]==0) continue;
        for(int n=d;n<=N;n+=d)
            f[n]+=mu[d]*(N/d-n/d);
    }
    int ans=1;
    for(int n=2;n<=N;n++)
        ans=1ll*ans*qpow(n,f[n])%mod;
    printf("%d\n",ans);
}