Codeforces Round #426 (Div. 1) A. The Meaningless Game

110 阅读 0 评论 73 点赞

我是靠谱客的博主霸气香烟，这篇文章主要介绍Codeforces Round #426 (Div. 1) A. The Meaningless Game，现在分享给大家，希望可以做个参考。

Problem

定义 one game 有 multiple rounds （might be 0）。对于 every round，胜利的人分数乘以 k2 ，失败的分数乘以 k 。两人在 game 开始是的分数均为 1 。

N 个询问，每组询问 a b 分别代表两人 one game 的最终分数。问该 a b 是否存在可能为真实分数 ?

Limit

1≤N≤350000

1≤a,b≤109

其中 k 为自然数。

Idea

对于分数 a b 可分别表示成下列形式：

a=k21⋯k2i⋅ki+1⋯ki+j ，
b=k1⋯ki⋅k2i+1⋯k2i+j

故 a×b=(k1⋯ki⋅ki+1⋯ki+j)3=K3 ，且 a 和 b 一定能被 K 整除。

故二分获取 K=a×b−−−−√3 （或者通过 std::cbrt() 获取立方根）。判断是否满足上述条件。

Code

复制代码

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
#include<bits/stdc++.h>
using namespace std;
long long Sqrt3(long long x) {
long long l = 1, r = min(x, (long long)1000000), val, mid;
while(l <= r) {
mid = (l+r) >> 1;
val = mid * mid * mid;
if(val > x) r = mid - 1;
else if(val < x)
l = mid + 1;
else
return mid;
}
return -1;
}
int main()
{
int n;
long long a, b, sumK;
scanf("%d", &n);
for(int i=1;i<=n;i++)
{
scanf("%lld %lld", &a, &b);
sumK = Sqrt3(a*b);
if(sumK == -1)
printf("Non");
else {
if(a % sumK || b % sumK)
printf("Non");
else {
a /= sumK;
b /= sumK;
if(a * b != sumK)
printf("Non");
else
printf("Yesn");
}
}
}
}