結果

問題 No.25 有限小数
ユーザー ayame_pyayame_py
提出日時 2016-01-07 13:06:01
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 1,495 bytes
コンパイル時間 1,603 ms
コンパイル使用メモリ 171,096 KB
実行使用メモリ 8,696 KB
最終ジャッジ日時 2023-10-19 16:22:21
合計ジャッジ時間 8,660 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 4 ms
4,348 KB
testcase_05 AC 251 ms
4,348 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

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