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

时间:2022-12-19 16:46:02

题目网址: 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;
}