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!