11327 - Enumerating Rational Numbers

[Saul Hidalgo]

Hi! In this problem i got TLE, i thought in dp, but.... i don't know very well the DP, and, in my program is of little help, because the delay a great time in compute the greatest number. Somebody can advise some idea, here is my code. Very thanks to all. .

Code: Select all

#include <iostream>

using namespace::std;

int almacen()

int gcd(register int a, register int b){
   register int t;
   while (b != 0){
      t = b;
      b = a%b;
      a = t;
   }
   return a;
}

bool resolver(int &numero){
   int cantidad=0;
   for (int d=1 ; true ; d++){
      for (int n=0; n<=d ; n++){
         if (gcd(n,d)==1)
            ++cantidad;
         if (cantidad==numero){
            cout << n << "/" << d << endl;
            return true;
         }
      }
   }
   return true;
}

int main(){
   int numero;
   while ((cin >> numero) && (numero!=0))
      resolver(numero);
   return 0;
}


[mpi]

Brute force is quite slow for this problem. Think that k can be greater than 10^9. I'll give you two hints:

* Euler's Phi Function (aka totient function):
http://es.wikipedia.org/wiki/Funci%C3%B ... 6_de_Euler (spanish)
* Binary search

[fayyaz]

It is enough to use Euler's Totient ... it will get it in time

[mostafiz93]

i'm getting WA in this problem.
can anybody find any bug in my code?

my code is here :

Code: Select all

Removed After AC


[magurmach]

Zero will be the last input so need not to be processed!
Better remove your code!