Euler's totient function practice code fails in online judge

Question

This is specifically UVA problem number 11327:

Given a series of all rational numbers between 0 and 1 (0/1, 1/1, 1/2, 1/3, 2/3,..., n/d) print the k-th fraction

I've used their debugger and my program outputs the exact same answers they give but the judge still marks it as incorrect.

I'm using Euler's totient function to find the denominator and iterating through GCDs that equal 1 to find the numerator. As far as I could find online, this should suffice.

Any help would be appreciated.

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
using namespace std;

//Calculate the greatest common divisor of a and b
long long GCD(long long a, long long b){
    if (a == 0){
        return b;
    }
    return GCD(b%a, a);
}

int main(){
    long long input;
    vector <long long> inputVector;
    vector <long long> phiValues;
    long long totient;
    long long total;
    int numerator;
    int denominator;

    while(cin >> input){
        if(input == 0){
            break;
        }
        inputVector.push_back(input);
    }

    // Calculate phi for all integers from 1 to
    // 20000 and store them 
    for(int i = 1; i <= 200000; i++){
        long long current = i;
        totient = current;
        for(long long k = 2; k <= sqrt(i); k++){
            if(current % k == 0){
                totient -= totient / k;
                while(current % k == 0){
                    current /= k;
                }
            }
        }
        if(current > 1){
            totient -= totient / current;
        }
        phiValues.push_back(totient);
    }

    for(int i = 0; i < inputVector.size(); i++){
        long long N = inputVector[i];
        total = 1;
        for(int j = 0; j <= phiValues.size(); j++){
            if(total >= N){
                if(N == 1){ //For the case of N = 1
                    denominator = 1;
                }else{ 
                    denominator = j; 
                }
                total -= phiValues[j-1]; 
                break;
            }
            total += phiValues[j];

        }
        int index = 0;
        for(int j = 1; j <= denominator; j++){
            if(GCD(j, denominator) == 1){
                index++;
                if(index == N - total){
                    numerator = j;
                    break;
                }
            }
        }
        cout << numerator << '/' << denominator << endl;
    }
    return 0;
}

If your goal of going to such sites is to learn C++, I recommend you stop at once. Instead [get a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and learn from them. You make at least one cardinal mistake that a good book should have told you not to do: Global variables. Global variables, especially when you don't need to share data between functions, is a bad practice. — Some programmer dude, Mar 02 '18 at 08:37
Duely noted. Thanks. I edited my code to get rid of them. And my goal isn't to learn C++. I have a fair grasp of it already. This is just me not understanding what makes my output correct to the debugger but not to the judge — user2953932, Mar 02 '18 at 08:57
Online judges not just test your code against the "demo test cases" they expose to you, they are just examples. But it tests also your code against some scaling-up issues, like for example, give it large numbers and tests your code not to pass the memory/time limit for example. So, make sure your code actually scales-up and you handle corner cases covered by the tests of your problem. — user9335240, Mar 02 '18 at 09:27
`k <= sqrt(i);` can be improved. Evaluate once, better still use `k * k <= i` and guard against overflow possibility. — Bathsheba, Mar 02 '18 at 09:45
Does the judge tell you if you *didn't pass the tests in time*, or if you gave a *wrong calculation*? On timing, they give you 3 seconds (on a CPU of unspecified nature). The example tests the largest input, so issue is not scaling that value up. They tell you you're going to get a "series of numbers" but not how many, so if there's a scaling point it's that: maybe it's a really long series. I definitely think they should tell you if you exceeded the time limit or not, submit a test that is just an infinite loop and make sure they'd tell you if so. — HostileFork says dont trust SE, Mar 02 '18 at 12:34
No, it's within the time restriction. The exact output is "wrong answer". — user2953932, Mar 02 '18 at 20:12

score 0 · Answer 1 · answered Mar 02 '18 at 16:19

Here @jte states that calculation of PHI can be achieved in O(N*logN):

phi[0]  = phi[1] = 0;
for (int i=2; i<maxn; ++i)
    phi[i] = i - 1;
for (int i=1; i<maxn; ++i)
        for (int j=i+i; j<maxn; j+=i)
                 phi[j] -= phi[i];

I could not find problem of your code. May be it is TLE (time limit exceeded) problem, because you should use binary search to find denominator. But this code will get ACCEPTED:

#include<bits/stdc++.h>

using namespace std;

const int N = 200031;

int pr[N+31],phi[N+31];
vector<int> P[N+31];
long long S[N+31];

int count(int n,int X)
{
    int res=n;
    int N=P[X].size();
    for (int mask=1;mask<(1<<N);mask++) {
        int C=0;
        int prod=1;
        for (int j=0;j<N;j++)
            if (mask&(1<<j))
                C++,
                prod*=P[X][j];
        if (C%2)
            res-=n/prod;
        else
            res+=n/prod;
    }
    return res;
}

int solve(int need,int val)
{
    int l,r;
    l=1;
    r=val;
    while (l<r) {
        int mid=l+r;
        mid/=2;
        int Q=count(mid,val);
        if (Q>=need)
            r=mid;
        else
            l=mid+1;
    }
    return l;
}

int main()
{
    ios_base::sync_with_stdio(0);

    pr[1]=1;
    for (int i=1;i<=N;i++) {
        if (pr[i])
            continue;
        for (int j=i;j<=N;j+=i)
            P[j].push_back(i),
            pr[j]=1;
    }

    for (int i=1;i<=N;i++) {
        phi[i]=i;
        for (int j=0;j<P[i].size();j++) {
            int val=P[i][j];
            phi[i]=phi[i]/val*(val-1);
        }
    }
    for (int i=1;i<=N;i++)
        S[i]=S[i-1]+phi[i];

    long long x;
    while (cin>>x) {
        if (x==0)
            break;
        --x;
        if (x==0)
        {
            cout<<0<<"/"<<1<<endl;
            continue;
        }
        int id=lower_bound(S+1,S+N+1,x)-S;
        x-=S[id-1];
        int ps=solve(x,id);
        cout<<ps<<"/"<<id<<endl;
    }

    return 0;
}

Euler's totient function practice code fails in online judge

1 Answers1