codeforces834CTheMeaninglessGame思维

题意&＃xff1a;

有n(1<&＃61;n<&＃61;350000)场游戏&＃xff0c;对于每场游戏有若干个回合组成&＃xff0c;两个人的初始分均为1&＃xff0c;每个回合赢的人当前分数乘上k^{2&＃xff0c;输的人当前分数乘上k(每一回合的k都是不同的)。给你两个数a,b(1<&＃61;a,b<&＃61;10}9)问你这两个数是否为他们最终的分数&＃xff1f;

思路&＃xff1a;在满足题意的情况下&＃xff0c;首先我们发现每次一个数K一共出现了三次&＃xff0c;一个数两次&＃xff0c;另一个数一次&＃xff0c;那么两个乘在一起就应该是k^3,那么总分相乘后首先满足的应该是这个数可分解成某个基数的三次方&＃xff0c;那么我们先判断开三次方后乘回去能否和原来的乘积相等。

a &＃61; k1^2 X k2 X k3^2 X k4 (a 1和3回合赢&＃xff0c;所以乘k的平方,2 4 输 乘k,X为乘号)

b &＃61; k1 X k2^2 X k3 X k4^2(b 2和4回合赢&＃xff0c;所以乘k的平方&＃xff0c;1 3 输 乘k)

a * b &＃61; k1^3 X k2^3 X k3^3 X k4^3 &＃61; (k1k2k3k4)^3

我们要得到的就是k1k2k3k4这个基数

但是这样并不能完全说明它是符合情况的&＃xff0c;因为并不能判断出K分在两个人的分数中&＃xff0c;如果一个K^3全都在一个人的分数中&＃xff0c;相乘后仍然可以分成某个数的三次方&＃xff0c;但却是不满足题意的。

a &＃61; k1^3 X k2 X k3^2 k4

b &＃61; k2^2 X k3 X k4^2

a * b &＃61; k1^3 X k2^3 X k3^3 X k4^3 &＃61; (k1k2k3k4)^3

这种情况即使a*b满足条件但是却无法得到&＃xff0c;这个时候我们发现基值是k1k2k3k4如果按照规则得到的分数&＃xff0c;每个分数肯定都包含了k1k2k3k4这几个数字&＃xff0c;那么直接每个人的分数再检验下是否能被整除就好了

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){ll x,y;scanf("%lld%lld",&x,&y);ll mul&＃61;x*y;ll i,temp;i&＃61;(ll)pow(1.0*mul,1.0/3);for(i--;;i&＃43;&＃43;){temp&＃61;i*i*i;if(temp>&＃61;mul)break;}if(temp&＃61;&＃61;mul&&x%i&＃61;&＃61;0&&y%i&＃61;&＃61;0)printf("YES\n");else printf("NO\n");}return 0;
}