P8015题解

lichengyun · 2022-07-02 16:53:03 · 题解

看到没人发题解，就来水一发（doge)

P8015题目

题意翻译：有k个真分数集 S_1 , S_2 , \ldots , S_n ，

式中，对 \forall i(i \in [1,n] ) 都有 S_i= \lbrace \frac{1}{i} , \frac{2}{i} , \ldots , \frac{n-1}{i} \rbrace。

求 |S_1 \cup S_2 \cup \ldots S_n|。

解法：考虑对每一个分数，都将其简化为既约分数。对于一个给定的整数 x (x > 1)，共有 φ(i) 个既约真分数以 x 为分母。

又对于一个给定的分数，显然有且仅有一个既约分数等于原数。

于是我们这就得到了本题的正解！

枚举每一个 A_i 的约数集合。对于不同集合中的相同约数 d_j，只计算其贡献 φ(d_j) 一次。

代码：

#include <bits/stdc++.h>
using namespace std;
bool v[1919810];
bool vis[314514];
int pr[29999],phi[314514],ptr=0;
int euler(int n){//线筛，筛phi函数
    memset(v,1,sizeof(v));
    v[0]=v[1]=false;
    for(int i=2;i<=n;i++){
        if(v[i]){
            pr[ptr++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<=ptr && (pr[j]*i<n);j++){
            v[i*pr[j]]=false;
            phi[i*pr[j]]=phi[i]*phi[pr[j]];
            if(i%pr[j]==0){
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
        }
    }
    return 0;
}
int main(int argc,char *argv[]){
    ios::sync_with_stdio(0);
    euler(131072);
    int n,ans=0;cin>>n;n++;
    while(n--){
        int A;cin>>A;//每次处理一个数
        for(int i=1;i*i<=A;i++){
            if(A%i==0){
                int j=A/i;
                //判重+算贡献
                ans+=(1-vis[i])*phi[i];vis[i]=1;
                ans+=(1-vis[j])*phi[j];vis[j]=1;
                cout<<i<<' '<<j<<'\n';
            }
        }
    }

    cout<<ans;
    return 0;
}