結果

問題 No.2954 Calculation of Exponentiation
コンテスト
ユーザー 👑 ygussany
提出日時 2024-11-08 21:47:12
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,052 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 21:47:14
合計ジャッジ時間 1,237 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b)
{
	if (a == 0) return b;
	else return gcd(b % a, a);
}

typedef struct {
	int numer, denom;
} ratio;

void reduce_ratio(ratio *a)
{
	int g = gcd(abs(a->numer), abs(a->denom));
	a->numer /= g;
	a->denom /= g;
	if (a->denom < 0) {
		a->numer *= -1;
		a->denom *= -1;
	}
}

int is_integer_ratio(ratio a)
{
	reduce_ratio(&a);
	if (a.denom == 1) return 1;
	else return 0;
}

int main()
{
	char A[15], B[15];
	scanf("%s", A);
	scanf("%s", B);
	
	int i;
	ratio a, b;
	for (i = 0, a.numer = 0; A[i] != '.'; i++) a.numer = a.numer * 10 + A[i] - '0';
	for (i++; A[i] != 0; i++) a.numer = a.numer * 10 + A[i] - '0';
	a.denom = 10000;
	for (i = (B[0] == '-')? 1: 0, b.numer = 0; B[i] != '.'; i++) b.numer = b.numer * 10 + B[i] - '0';
	for (i++; B[i] != 0; i++) b.numer = b.numer * 10 + B[i] - '0';
	b.denom = 10000;
	if (B[0] == '-') {
		a.denom ^= a.numer;
		a.numer ^= a.denom;
		a.denom ^= a.numer;
	}
	reduce_ratio(&a);
	reduce_ratio(&b);
	if (b.numer == 0) {
		printf("Yes\n");
		return 0;
	}

	long long l, r, m;
	while (b.denom % 2 == 0) {
		b.denom /= 2;
		l = 1;
		r = a.numer;
		while (l < r) {
			m = (l + r) / 2;
			if (m * m < a.numer) l = m + 1;
			else r = m;
		}
		if (l * l == a.numer) a.numer = l;
		else {
			printf("No\n");
			return 0;
		}
		
		l = 1;
		r = a.denom;
		while (l < r) {
			m = (l + r) / 2;
			if (m * m < a.denom) l = m + 1;
			else r = m;
		}
		if (l * l == a.denom) a.denom = l;
		else {
			printf("No\n");
			return 0;
		}
	}
	while (b.denom % 5 == 0) {
		b.denom /= 5;
		l = 1;
		r = a.numer;
		while (l < r) {
			m = (l + r) / 2;
			if ((__int128)m * m * m * m * m < a.numer) l = m + 1;
			else r = m;
		}
		if (l * l == a.numer) a.numer = l;
		else {
			printf("No\n");
			return 0;
		}
		
		l = 1;
		r = a.denom;
		while (l < r) {
			m = (l + r) / 2;
			if ((__int128)m * m * m * m * m < a.denom) l = m + 1;
			else r = m;
		}
		if (l * l == a.denom) a.denom = l;
		else {
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	fflush(stdout);
	return 0;
}
0