Yukicoder025 有限小数

問題概要

$N$,$M$が与えられる。このとき$\displaystyle\frac{N}{M}$は有限小数か。 またそのとき、0でない一番小さい桁の数字を出力せよ。

$1\leqq N,M\leqq9,223,372,036,854,775,807$

yukicoder025

解法

いい感じの$k$に対して、$\displaystyle \frac{N}{M} * 10^k$が整数になるならもとの分数は有限小数であることから考える。 約分は$N$、$M$の最大公倍数で行えば良い。判定自体は$M$の素因数が2または5のみであれば有限小数である。
0でない最下位の数字は、$\displaystyle \frac{N}{M} * 10^k$をもう一度考える。
小数点があってもなくても関係ないので、分母の2,5の数に合わせて大きい方を$k$とする。 実際に$10^k$をかけた数字が末尾の数字となる。

計算量:$O(logM+logN)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    
    LL N, M;
    LL ans = 0LL;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        cin >> N >> M;
    
        LL g = __gcd(N, M);
        N = N / g; M = M / g;
        LL MM = M;
        int cnt2 = 0, cnt5 = 0;
        while (MM % 2 == 0) {
            MM /= 2;
            cnt2++;
        }
        while (MM % 5 == 0) {
            MM /= 5;
            cnt5++;
        }
        if (MM != 1) {
            cout << -1 << endl;
        }
        else { // 有限小数
            while (N % 10 == 0) {
                N /= 10;
            }
            N = N % 10;
            for (; cnt2 > 0 || cnt5 > 0; cnt2--, cnt5--) {
                if (cnt2 <= 0)N = (N * 2) % 10;
                if (cnt5 <= 0)N = (N * 5) % 10;
            }
            cout << N << endl;
        }
    
        return 0;
    }