## 11327 - Enumerating Rational Numbers

Moderator: Board moderators

### 11327 - Enumerating Rational Numbers

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;}`
Saul Hidalgo
New poster

Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela

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

Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm

### Re: 11327 - Enumerating Rational Numbers

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

Posts: 1
Joined: Sat Jul 02, 2011 11:28 pm

### Re: 11327 - Enumerating Rational Numbers

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`
Last edited by mostafiz93 on Tue Jun 12, 2012 4:02 pm, edited 1 time in total.
mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 11327 - Enumerating Rational Numbers

Zero will be the last input so need not to be processed!