yukicoder no.25

問題文
http://ch.nicovideo.jp/programing/blomaga/ar620922

解説（と考えた過程）
有限小数で表せるということは、分子を整数、分母を 10^n で表せるということである。
分母が 10^n すなわち (2^n) * (5^n) で表せるためには、M が 2 または 5 の素因数のみを持つことが必要である。後は、2 と 5 の素因数の少ない方を N にかけてやれば、元の分数 N / M を (整数) / (10^n) という形で表すことができるようになる。

ただここで、普通にやるとオーバーフローしてしまう。求める解が、小数点を含めて下の桁から見て trailing 0 を取り除いた最後の数字なので、N % 10 のみの計算をひたすら考えていけばよい…と思う、がジャッジをまだ通せていないので正答かどうか不明。
問題作成者である yuki2006 様に記事を見て頂いて以下のコードで無事 AC を頂きました。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll mod_pow(ll x, ll n, ll MOD) {
  if(n == 0) return 1;
  ll ret = mod_pow(x*x%MOD, n/2, MOD);
  if(n&1) (ret *= x) %= MOD;
  return ret;
}

int main() {
  
  ll N, M;
  cin >> N >> M;
  
  ll GCD = __gcd(N, M);
  N /= GCD, M /= GCD;
  
  if(M == 1) {
    while(N % 10 == 0 && N > 0) {
      N /= 10;
    }
    cout << N%10 << endl;
    return 0;
  }
  
  ll TWO = 0;
  ll FIVE = 0;
  while(M % 2 == 0) TWO ++, M /= 2;
  while(M % 5 == 0) FIVE ++, M /= 5;

  if(M != 1) {
    cout << -1 << endl;
    return 0;
  }
  
  N %= 10;
  
  if(TWO == FIVE) {
    cout << N << endl;
  }
  else {
    ll b = TWO < FIVE ? 2 : 5;
    cout << N * mod_pow(b, abs(TWO - FIVE), 10) % 10 << endl;
  }
  
  return 0;
}