結果

問題 No.25 有限小数
コンテスト
ユーザー ayame_py
提出日時 2016-01-07 13:06:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,495 bytes
コンパイル時間 3,006 ms
コンパイル使用メモリ 169,200 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-09-19 12:28:21
合計ジャッジ時間 10,456 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i < (ll)(m); i++)
#define INF 1000000007

typedef long long ll;

ll N, M;
map<ll,ll> prime;
map<ll,ll> prime2;

// 素因数分解
// 試し割り
void prime_decomposition(){
    ll n = N;
    FOR(i,2,sqrt(N)+2){
        while(n%i==0){
            prime[i]++;
            n/=i;
        }
    }
    if(n!=1) prime[n]++;
}
void prime_decomposition2(){
    ll n = M;
    FOR(i,2,sqrt(M)+2){
        while(n%i==0){
            prime2[i]++;
            n/=i;
        }
    }
    if(n!=1) prime2[n]++;
}


int main(){
    cin >> N;
    cin >> M;
    
    // 整数の時
    if (double(N/M)==N/double(M)){
        ll t = N/M;
        while(true){
            if(t%10!=0){
                cout << t%10 << endl;
                return 0;
            }else{
                t/=10;
            }
        }
    }
    // 小数の時
    prime_decomposition();
    prime_decomposition2();
    
    // 約分
    for(auto x: prime2){
        // 循環小数
        if (prime[x.first]<x.second && x.first!=5 && x.first!=2){
            cout << -1 << endl;
            return 0;
        }
        prime2[x.first]-=min(x.second,prime[x.first]);
        REP(i,min(x.second,prime[x.first])) N/=x.first;
    }
    
    if(prime2[5]>prime2[2]) REP(i,prime2[5]-prime2[2]) {N*=2; N%=10;}
    else REP(i,prime2[2]-prime2[5]) {N*=5; N%=10;}
    
    cout << N << endl;
    
    return 0;
}
0