SPOJ GAMES Solution

| July 01, 2015

The correct, optimal and working solution for programming question GAMES on spoj

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>

using namespace std;

map<int,int> prime_factors( long long int n ) {
	map<int,int> fact;

	while ( n % 2 == 0 ) {
		if ( fact.count(2) == 0 ) {
			fact[2] = 0;
		}
		fact[2]++;
		n /= 2;
	}

	for ( int i = 3; i <= sqrt(n) ; i+=2 ) {
		while ( n % i == 0 ) {
			if ( fact.count(i) == 0 ) {
				fact[i] = 0;
			}
			fact[i]++;
			n /= i;
		}
	}

	if ( n > 2 ) {
		if ( fact.count(n) == 0 ) {
			fact[n] = 0;
		}
		fact[n]++;
	}

	return fact;
}

int readline( char * str ) {

	int i = 0;
	char ch;
	while ( (ch = getchar()) != '\n' ) {
		str[i++] = ch;
	}
	str[i] = '\0';
	return i;
}

int gcd ( int a , int b ) {

	while ( a != b ) {
		if ( a > b )
			a = a - b;
		else if ( b > a )
			b = b - a;
	}
	return a;
}

int main( int argc , char * argv[] ) {

	int t;
	char s[128];

	scanf("%d" , &t);
	getchar();

	while ( t-- ) {
		readline(s);

		int i;
		for ( i = 0 ; s[i] != '\0' ; i++ ) {
			if ( s[i] == '.' )
				break;
		}
		if ( s[i] == '.' ) {
			int power = 1;
			int num = 0;
			i++;
			for ( ; s[i] != '\0' ; i++ ) {
				num = num * 10 + (s[i]-'0');
				power *= 10;
			}
			printf("%d\n" , power/gcd(num,power) );
		}
		else {
			printf("1\n");
		}

	}
	return 0;
}