Skip to content

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行,每行输出一共YesNo

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

Sample Input

4
2 4
75 45
8 8
16 16

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;
}