結果

問題 No.25 有限小数
コンテスト
ユーザー bal4u
提出日時 2019-04-09 06:13:02
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 5,000 ms
コード長 2,204 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 29,568 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 22:58:59
合計ジャッジ時間 1,225 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: No.25 有限小数
// 2019.4.9 bal4u
// 有限小数の条件と求め方
// 
// 有限小数になる条件は簡単。分数を既約にして、分数である
// こと、分母の素因数が2と5しかないこと、の2つ。
//
// 最後のゼロでない桁の数値を筆算のような方法で計算したら、
// 厳しいテストデータでは、オーバーフローになり、通用しないようだ。
// たとえば、以下のテストデータではうまくいかない。
//    N=2873113840948988816
//    M=7450580596923828125
// 分子を10倍すると、64ビット整数ではオーバーフローになってしまうから。
//
// ということで、別の方法を考える。
// 1/2=0.5, 1/5=0.2 なので、
// 5のべき乗と2のべき乗と分子、それぞれ（10進数での）最後の桁との積算で正解を出せそう。

#include <stdio.h>

long long gcd(long long a, long long b)
{
	long long r;
	while (b != 0) r = a % b, a = b, b = r;
	return a;
}

int n2, n5;   // 素因数2と5のそれぞれの次数。200 -> n2=3, n5=2  200=2^(3) * 5^(2)
int calc_power(long long x)
{
	n2 = n5 = 0;
	while ((x & 1) == 0) n2++, x >>= 1;
	while (x % 5 == 0) n5++, x /= 5;
	return x == 1;
}

int b2[4] = { 6, 2, 4, 8 };  // 2のべき乗の最後の桁。2->4->8->16->32->64->128->256...

int main()
{
	int ans;
	long long N, M, g;

	scanf("%lld%lld", &N, &M);
	g = gcd(N, M), N /= g, M /= g;  // 既約化

	// N/M が整数であるケース
	if (N % M == 0) {
		N /= M;
		while ((ans = (int)(N % 10)) == 0) N /= 10;
	}

	// 有限小数にならないケース
	else if (!calc_power(M)) ans = -1;

	// 有限小数になるケース
	else {
		int n;  // 10進数で表す分子の、最後のゼロでない数値

		while ((n = (int)(N % 10)) == 0) N /= 10;

		if (n2 == n5)        // 分母を10進数有限小数にしたときの最後の桁が1
			ans = n;
		else if (n2 > n5)    // 分母に2の素因数が多いケース
			ans = (n * 5) % 10;   // 5のべき乗は最後の桁がつねに5
		else                 // 分母に5の素因数が多いケース
			ans = (n * b2[(n5 - n2) % 4]) % 10;
	}
	printf("%d\n", ans);
	return 0;
}
0