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

#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");
}
}
}
}

最后

以上就是霸气香烟为你收集整理的Codeforces Round #426 (Div. 1) A. The Meaningless Game的全部内容，希望文章能够帮你解决Codeforces Round #426 (Div. 1) A. The Meaningless Game所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。