No.25 有限小数 - yukicoder
- 高校時代を思い出した。こんな感じの問題解いた記憶があった。
- コメントのとおり overflow してしまった。くそー。
class FiniteDecimal {
public:
void solve(void) {
ll N,M;
cin>>N>>M;
ll g = gcd(N,M);
N /= g;
M /= g;
if (N % M == 0)
{
ll x = N/M;
while (x%10 == 0)
x /= 10;
cout<<x%10<<endl;
return;
}
int k1 = 0;
ll m = M;
while (m%5 == 0)
{
m /= 5;
++k1;
}
int k2 = 0;
while (m%2 == 0)
{
m /= 2;
++k2;
}
if (m == 1)
{
while (N % 10 == 0) N /= 10;
N %= 10;
while (k1 > 0)
{
N *= 2;
while (N % 10 == 0) N /= 10;
N %= 10;
--k1;
}
while (k2 > 0)
{
N *= 5;
while (N % 10 == 0) N /= 10;
N %= 10;
--k2;
}
while (N % 10 == 0) N /= 10;
cout<<N%10<<endl;
}
else
cout<<-1<<endl;
}
};