// yukicoder: No.25 有限小数 // 2019.4.9 bal4u // 有限小数の条件と求め方 // // 有限小数になる条件は簡単。分数を既約にして、分数である // こと、分母の素因数が2と5しかないこと、の2つ。 // // 最後のゼロでない桁の数値を筆算のような方法で計算したら、 // 厳しいテストデータでは、オーバーフローになり、通用しないようだ。 // たとえば、以下のテストデータではうまくいかない。 // N=2873113840948988816 // M=7450580596923828125 // 分子を10倍すると、64ビット整数ではオーバーフローになってしまうから。 // // ということで、別の方法を考える。 // 1/2=0.5, 1/5=0.2 なので、 // 5のべき乗と2のべき乗と分子、それぞれ(10進数での)最後の桁との積算で正解を出せそう。 #include long long gcd(long long a, long long b) { long long r; while (b != 0) r = a % b, a = b, b = r; return a; } int n2, n5; // 素因数2と5のそれぞれの次数。200 -> n2=3, n5=2 200=2^(3) * 5^(2) int calc_power(long long x) { n2 = n5 = 0; while ((x & 1) == 0) n2++, x >>= 1; while (x % 5 == 0) n5++, x /= 5; return x == 1; } int b2[4] = { 6, 2, 4, 8 }; // 2のべき乗の最後の桁。2->4->8->16->32->64->128->256... int main() { int ans; long long N, M, g; scanf("%lld%lld", &N, &M); g = gcd(N, M), N /= g, M /= g; // 既約化 // N/M が整数であるケース if (N % M == 0) { N /= M; while ((ans = (int)(N % 10)) == 0) N /= 10; } // 有限小数にならないケース else if (!calc_power(M)) ans = -1; // 有限小数になるケース else { int n; // 10進数で表す分子の、最後のゼロでない数値 while ((n = (int)(N % 10)) == 0) N /= 10; if (n2 == n5) // 分母を10進数有限小数にしたときの最後の桁が1 ans = n; else if (n2 > n5) // 分母に2の素因数が多いケース ans = (n * 5) % 10; // 5のべき乗は最後の桁がつねに5 else // 分母に5の素因数が多いケース ans = (n * b2[(n5 - n2) % 4]) % 10; } printf("%d\n", ans); return 0; }