Codeforces834C The Meaningless Game

题目描述:

Slastyona and her loyal dog Pushok are playing a meaningless game that is indeed very interesting.

The game consists of multiple rounds. Its rules are very simple: in each round, a natural number k is chosen. Then, the one who says (or barks) it faster than the other wins the round. After that, the winner's score is multiplied by k2, and the loser's score is multiplied by k. In the beginning of the game, both Slastyona and Pushok have scores equal to one.

Unfortunately, Slastyona had lost her notepad where the history of all n games was recorded. She managed to recall the final results for each games, though, but all of her memories of them are vague. Help Slastyona verify their correctness, or, to put it another way, for each given pair of scores determine whether it was possible for a game to finish with such result or not.

Input

In the first string, the number of games n (1 ≤ n ≤ 350000) is given.

Each game is represented by a pair of scores ab (1 ≤ a, b ≤ 109) – the results of Slastyona and Pushok, correspondingly.

Output

For each pair of scores, answer "Yes" if it's possible for a game to finish with given score, and "No" otherwise.

You can output each letter in arbitrary case (upper or lower).

题意:给定两个数,两个人做游戏,初始分数都为1,赢的一方分数乘k的二次方,数的乘k,问进行x轮后两个人的分数能不能成为给定的两个数。

分析:

  我们设一轮游戏后一方分数为a*k^2,另一方为b*k^2,那么该轮游戏后双方分数就为a*b*k^3,我们设第i轮游戏的分数为ki,那么最后游戏结束后双方分数之积为1*1*k1^3*k2^3*…*kn^3=(k1*k2*k3…*kn)^3;则若结果合法,给定两数的乘积一定是某个数的三次方(即k1*k2*k3…*kn),我们就可以通过开立方以求出这个数,又计分过程中一方乘k,一方乘k^2,那么最终结果一定都可以除尽k1*k2*k3…*kn;

综上,我们判断结果合法有两个条件:

1.乘积开立方得到整数;

2.1中得到的整数都是两个数的因数.

最后上代码:

Codeforces834C The Meaningless GameCodeforces834C The Meaningless Game
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 int main(){
 6     int n;
 7     scanf("%d",&n);
 8     while(n--){
 9         long long a,b;
10         scanf("%lld%lld",&a,&b);
11         long long ans=ceil(pow(a*b,1.0/3));  //向上取整 
12         if(ans*ans*ans==a*b&&a%ans==0&&b%ans==0)  //判断是否合法 
13             printf("Yes\n");
14         else
15             printf("No\n");
16     }
17     return 0;
18 }
View Code

 

上一篇:K2百家讲坛 | 越秀地产:K2为房企数字化转型带来更多可能


下一篇:K2 BPM_“流程平台可以解决哪些问题?”,企业关心的都在这里(二)