【Codeforces Round #426 (Div. 2) C】The Meaningless Game

95 阅读 0 评论 63 点赞

我是靠谱客的博主自然方盒，最近开发中收集的这篇文章主要介绍【Codeforces Round #426 (Div. 2) C】The Meaningless Game，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【Link】:http://codeforces.com/contest/834/problem/C

【Description】

有一个两人游戏游戏;
游戏包括多轮,每一轮都有一个数字k,赢的人把自己的分数乘上k2，输的人乘上k;
给你两个数字a,b;
问你第一个人的分数为a,第二个人的分数为b可不可能;

【Solution】

考虑最后的合法结果;
必然是这种形式
S2∗P=a
S∗P2=b
因为不是第一个人得k^2就是第二个人得k^2
如
k1^2*k2*k3^2
k1*k2^2*k3
上面S=k1*k3,P=k2
又有
a∗b=（S∗P)3
则设x=S∗P=(a∗b)13
然后带回最上面那个式子
S=ax
P=bx
则,需要判断a*b是否为立方数,然后判断x能否整除a,能否整除b即可;
都行则有解

【NumberOf WA】

6

【Reviw】

没能用合适的数学方法看待问题.

【Code】

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,a;
main(){
ios::sync_with_stdio(0);
scanf("%lld",&n);
for (int i = 1;i <= n;i++){
scanf("%lld%lld",&x,&y);
a = x*y;
int l = 1,r = 1e6,ans =-1;
while (l <= r){
int m = (l+r)>>1;
int temp = m*m*m;
if (temp <= a){
if (temp==a)ans = m;
l = m+1;
}else
r = m-1;
}
if (ans==-1 || x%ans || y % ans)
puts("NO");
else
puts("YES");
}
return 0;
}