(数学或二分)Codeforces Round #426 C. The Meaningless Game

题目网址: Codeforces Round #426 C. The Meaningless Game

题意分析:

题意:

• Slastyona 和 她的狗一起玩游戏, 每一场游戏包括很多轮(可能0轮)
• 初始她们的分数均为 1
• 她们选取一个数 k, 谁最先回答出来, 则她(它)的分数乘以k^2, 另一个人的分数乘以 k
• 但是n场游戏得分Slastyona记不太清楚, 给出n场游戏两个人(动物??)的得分, 问这个得分是否合理(即 是否存在一场游戏,使得她们可以达到这个得分)

思路:

• Slastyona 得分 为a, 她的狗得分为b
• 若得分合理, 则 满足 a*b = T^3 (因为她们的得分是一人乘以k^2, 一人乘以k, 所以得分合理的话, 就会有一个大T使得 a*b = T^3)
• 并且 a是能整除这个大T的, b 也是能整除这个大T的
• 题目转换为找这个大T

代码:

解法1: 直接用数学函数 cbrt开三次方根

#include <bits/stdc++.h>

using namespace std;

// 数学方法
int main(int argc, char const *argv[])
{
int n, a, b;

while (~scanf("%d", &n))
    {
for (int i = 0; i < n; ++i)
        {
scanf("%d %d", &a, &b);
int K = cbrt((double)a * (double)b);
int aa = a / K;
int bb = b / K;
puts((aa * aa * bb == a && bb * bb * aa == b) \
                 ? "Yes" : "No"); // 和思路表述的意思是一致的
        }
    }
return 0;
}

---

解法2: 用二分查找来找到满足的条件

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAX = 1e6+5;

// 二分
bool check(ll a, ll b)
{
    ll l = 1, r = MAX;

    ll cmp = a * b;
while (l <= r)
    {
        ll mid = (l+r)/2;
if(mid * mid * mid < cmp)
        {
            l = mid + 1;
        }
else r = mid - 1;
    }
if(l * l * l == cmp && !(a % l) && !(b % l)) return true;
else return false;
}

int main(int argc, char const *argv[])
{
int n;
    ll a, b;
while (~scanf("%d", &n))
    {
for (int i = 0; i < n; ++i)
        {
scanf("%I64d %I64d", &a, &b);
if(check(a, b)) printf("Yes\n");
else printf("No\n");
        }
    }
return 0;
}