yukicoder 0025 有限小数

概要

$m/n$ を $10$ 進数として書いたとき, 有限小数になるだろうか. なるならば, $0$ でない最後の桁の数字, ならないならば $-1$ を出力せよ.

すなわち, $m/n = X * 10^e$, $X \not \equiv 0 \pmod 10$, $e \in \Z$ と書けるか調べ, $X \bmod 10$ を出力せよ.

制約

$1 \le m, n \le 2^{63} - 1$.

解法

とりあえず $\gcd(m, n)$ で割り, $m/n$ が既約分数になるようにする. この表示で, $m/n$ が有限小数である事は, $n = 2^a 5^b$ と表せることと同値.

よって, 以下 $n = 2^a 5^b$ の場合を考えればよい.

さて, $m$, $n$ を $10$ 倍することは, それぞれ $m/n$ を $10$ 倍, $1/10$ 倍することと同値だから, $m$, $n$ は $10$ で割り切れなくなるまで割っておいてよい. すると, $n = 2^a,\ a \le 1$ または $n = 5^b,\ b \le 0$ と書ける.

• $n = 2^a$ の時, $m$ を $a$ 回 $2$ で割る事になるが, $\gcd(m, n) = 1$ から $m \equiv 1 \mod 2$ であり, 末尾は $5$ になる.

• $n = 5^b$ の時, 答えは $m * 2^b \bmod 10$ であるから, $m \bmod 10$ に $2$ を $b$ 回掛ければよい.

$n = 2^a$ の時も適当にループを回す事にしてしまうと, $m$, $n$ に $5^a$ 又は $2^b$ を掛けて, $n$ を $10^a$ 又は $10^b$ にしてしまうと思えば, ちょっとはしょれる? そうでもないかなぁ.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool solve(){
    ll n, m;
    cin >> n >> m;
    ll g = __gcd(n, m);
    n /= g; m /= g;
    while(m % 10 == 0) m /= 10;
    while(n % 10 == 0) n /= 10;
    n %= 10;
    for(; m % 2 == 0; m /= 2) (n *= 5) %= 10;
    for(; m % 5 == 0; m /= 5) (n *= 2) %= 10;
    if(m != 1) n = -1;
    cout << n << endl;
    return true;
}