Uva 11327 Solution

#include<bits/stdc++.h>

#define ll long long int

#define N 200010

using namespace std;

bitset<N+10>p;

vector<ll>phi(N+10);

void prime()

{

p[0] = p[1] = 1;

for(int i=2;i*i<=N;i++)

{

if(p[i] == 0)

{

for(int j=2; i*j<=N; j++)

p[i*j] = 1;

}

}

}

void phi_function()

{

phi[1] = 2;

for(ll i=2;i<=N;i++)

phi[i] = i;

for(ll i=2; i<=N; i++)

{

if(p[i] == 0)

{

for(ll j=i; j<=N; j+=i)

phi[j] = phi[j]/i*(i-1);

}

}

for(ll i=2;i<=N;i++)

phi[i] += phi[i-1];

}

int main()

{

prime();

phi_function();

ll n;

while(cin >> n && n > 0)

{

if(n == 1)

{

cout << "0/1" << "\n";

continue;

}

else if(n == 2)

{

cout << "1/1" << "\n";

continue;

}

ll denominator = lower_bound(phi.begin(), phi.end(), n) - phi.begin();

ll number = n - phi[denominator - 1];

int c = 0;

for(ll i=1;i<=denominator; i++)

{

if(__gcd(i, denominator) == 1)

c++;

if(c == number)

{

cout << i << "/" << denominator << "\n";

break;

}

}

}

return 0;

}