pta
牛客

H. 游戏

最后答案即为\(\frac{互质的对数}{n}\)。

Code

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int MAXN = 5e3+5,MAXM = 1e6+5,MOD = 998244353,INF = 0x3f3f3f3f,N=2e5;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
const db eps = 1e-7;
#define lson o<<1,l,m
#define rson o<<1|1,m+1,r
#define mid l + ((r-l)>>1)
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
#define x first
#define y second
using namespace std;

int n,primes[MAXN],phi[MAXN],cnt,sum[MAXN];
void init(){
    phi[1] = 1;
    for(int i=2;i<=5000;i++){
        if(!phi[i]){
            primes[cnt++] = i;
            phi[i] = i-1;
        }
        for(int j=0;j<cnt&&primes[j]*i<=5000;j++){
            if(i%primes[j]==0){
                phi[i*primes[j]] = phi[i]*primes[j];
                break;
            }
            phi[i*primes[j]] = phi[i] * (primes[j]-1);
        }
    }
    for(int i=2;i<=5000;i++)sum[i] = sum[i-1] + phi[i];
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    init();
    cin>>n;
    if(n==2){
        cout<<1<<'/'<<1<<'\n';
        return 0;
    }else if(n==1){
        cout<<0<<'/'<<1<<'\n';
        return 0;
    }
    int a = sum[n];
    int b = (n&1?n:n-1);
    int g = gcd(a,b);
    cout<<a/g<< '/'<<b/g<<'\n';
    return 0;
}