当前位置：网站首页>CodeForces-834C

CodeForces-834C

2022-08-10 13:19:00 【51CTO】

Slastyona and her loyal dog Pushok are playing a meaningless game

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 k², 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

Input

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

Each game is represented by a pair of scores a, b (1 ≤ a, b ≤ 10⁹)

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).

Example

Input

       
       6
       
4
       
45
       
8
       
16
       
994
       
1000000000 1000000
      








Output

       
       Yes
       
Yes
       
Yes
       
No
       
No
       
Yes
      
1.
2.
3.
4.
5.
6.

题目大概：

Two people talking numbers,Whoever is bigger wins,The winning team's score is multiplied by the square of the larger number,Multiply the lost fraction by the larger number,Know the two scores first,Ask if the match rating is correct.（Games can have multiple rounds）

思路：

When a round,Multiply two fractions to the third power of a large number,when multiple rounds,也成立,It is the cube of the product of multiple rounds of large numbers.Use binary to find the final value,Check if the value is correct,并输出结果.

代码：

       
       #include <iostream>
       
       #include <string>
       
       #include <queue>
       
       #include <cstring>
       
       #include <cstdio>
       
       using 
       
       namespace 
       
       std;
       
       long 
       
       long 
       
       go(
       
       long 
       
       long 
       
       sum)
       
{
       
       long 
       
       long 
       
       l,
       
       r;
       
       l
       
       =
       
       0;
       
       r
       
       =
       
       1000000;
       
       while(
       
       l
       
       !=
       
       r)
       
   {
       
       long 
       
       long 
       
       mid
       
       =(
       
       l
       
       +
       
       r
       
       +
       
       1)
       
       /
       
       2;
       
       if(
       
       mid
       
       *
       
       mid
       
       *
       
       mid
       
       >
       
       sum){
       
       r
       
       =
       
       mid
       
       -
       
       1;
       
       }
       
       else {
       
       l
       
       =
       
       mid;
       
       }
       
   }
       
       return 
       
       l;
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       t;
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       t;
       
       i
       
       ++)
       
{
       
       long 
       
       long 
       
       n,
       
       m;
       
       scanf(
       
       "%I64d%I64d",
       
       &
       
       n,
       
       &
       
       m);
       
       long 
       
       long 
       
       g
       
       =
       
       go(
       
       n
       
       *
       
       m);
       
       if(
       
       g
       
       *
       
       g
       
       *
       
       g
       
       !=
       
       n
       
       *
       
       m)
       
       printf(
       
       "No\n");
       
       else 
       
       if(
       
       n
       
       %
       
       g
       
       ==
       
       0
       
       &&
       
       m
       
       %
       
       g
       
       ==
       
       0)
       
       printf(
       
       "Yes\n");
       
       else 
       
       printf(
       
       "No\n");
       
}
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/222/202208101223192133.html

当前位置：网站首页>CodeForces-834C

CodeForces-834C

边栏推荐

猜你喜欢

随机推荐