14066: 【原4066】王马小吉的谎言

题目

题目描述

author: 陈竞潇原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4066

Background

在才囚学园中，进行着残酷的自相残杀游戏。想要活下去，就必须在学级裁判中找到真正的凶手。

然而喜欢说谎的王马小吉总是会想方设法制造伪证干扰大家。

为了找到真相，你——超高校级的计算机科学家必须揭穿他的谎言！

Description

小吉提供了一份和Alter Ego的游戏对战记录作为自己的不在场证明。

每一局游戏开始时，小吉和Alter Ego各自的分数为1。

在一局游戏过程中，两人会进行若干次赌博猜拳。

每一次猜拳，两人会先确定一个正整数\(K\)，然后进行猜拳。获胜的一方的分数乘以\(K^2\)，而输的一方的分数乘以\(K\)。

（注意每一次猜拳选取的K可以不同）

然而这份记录仅包括了n局游戏每轮最后小吉和Alter Ego各自的得分，对于每一条得分数据，请你判断是否可能存在一局游戏能得到这样的结果。

Input Format

第1行是一个整数\(n\)，代表一共进行了n轮游戏。

接下来n行，每行2个整数\(a\)和\(b\)，表示这一局小吉和Alter Ego各自的得分

Output Format

输出n行，每行输出一共Yes或No。

Yes表示这局游戏可能存在，No表示一定不存在这样的游戏。

Sample Input

Sample Output

Yes
Yes
Yes
No

Limits

对于前20%的数据，保证\(n=1\)。
对于前50%的数据，保证如果游戏存在，则\(K=2\)。
对于前70%的数据，\(1\le n\le 100\), \(1\le a,b\le1000\)。
对于100%的数据，\(1\le n\le 200000\), \(1\le a,b\le10^9\)。

Hint

请注意，对于n较大数据，请对I/O操作进行优化。

对于大数据建议尽量使用整数类型，避免产生精度误差。

Hint 2

王马小吉最讨厌说谎和开玩笑，因此本题数据严格按照Limits所给上限生成，并且保证所有错误的做法都拿不到分数。

当然，这是骗你的。

FineArtz's solution

/* 王马小吉的谎言 */
#include <iostream>
#include <cmath>
using namespace std;

long long sqr3(long long x){
    long long l = 2, r = 1000000, mid;
    while (l <= r){
        mid = (l + r) / 2;
        if (mid * mid * mid == x) return mid;
        if (mid * mid * mid > x) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--){
        long long a, b;
        cin >> a >> b;
        if (a == 1 && b == 1){
            cout << "Yes" << '\n';
            continue;
        }
        long long t = a * b;
        long long sq = sqr3(t);
        if (sq == -1){
            cout << "No" << '\n';
            continue;
        }
        if (a % sq == 0 && b % sq == 0){
            cout << "Yes" << '\n';
        }
        else cout << "No" << '\n';
    }
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll root3(ll x)
{
    ll l=1,r=1000000,m;
    while (l<=r)
    {
        m=(l+r)/2;
        if (m*m*m==x) return m;
        if (m*m*m<x) l=m+1;
        else r=m-1;
    }
    return 0;
}
ll a,b,t;
int n;
int main() {
    scanf("%d",&n);
    for (int i=0;i<n;++i)
    {
        scanf("%lld%lld",&a,&b);
        if (!(t=root3(a*b))||a%t||b%t)
        {
            printf("No\n");
            continue;
        }
        printf("Yes\n");
    }
    return 0;
}