Codeforces 834C

834C - The Meaningless Game

数学。

思路1：判断a•b能不能化成v³且a%v==0且b%v==0。v可以直接用pow求（或者用cbrt），也可以二分求；还可以用map映射预处理，使得所有的map[v*v*v]=v。

代码1(cbrt版，296 ms)：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e6+5;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
map<ll,ll>mp;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        ll m=a*b;
        ll v=cbrt((ld)m);
        ll x=a/v,y=b/v;//a*b==x*y*v*v==v*v*v得出v=x*y
        if(x*x*y==a&&x*y*y==b)puts("Yes");
        else puts("No");
    }
    return 0;
} 

代码2（pow版，311 ms）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e5+5;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        ll m=a*b;
        ll v=pow(m,1./3);
        while(v*v*v<m)v++;
        if(v*v*v!=m||a%v!=0||b%v!=0)puts("No");
        else puts("Yes");
    }
    return 0;
} 

 代码3（二分版，327 ms）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e6+5;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        ll m=a*b;
        int l=0,r=N;
        ll mid;
        while(l<r)
        {
            mid=(l+r)>>1;
            if(mid*mid*mid<a*b)l=mid+1;
            else r=mid;
        }
        ll v=mid;
        while(v*v*v<m)v++;
        if(v*v*v!=m||a%v!=0||b%v!=0)puts("No");
        else puts("Yes");
    }
    return 0;
} 

 代码4（map版，717 ms）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e6+5;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
map<ll,ll>mp;
int main()
{
    int n;
    for(ll i=1;i<N;i++)mp[i*i*i]=i;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        ll m=a*b;
        if(!mp[m])puts("No");
        else 
        {
            if(a%mp[m]||b%mp[m])puts("No");
            else puts("Yes");
        }
    }
    return 0;
} 

思路2：gcd(a,b)=∏ki^aki(1≤aki≤2),a•b=∏ki³。先看a•b能不能化成v³,如果不能输出No;否则，因为c=gcd(gcd(a,b),a•b)肯定包含了∏ki，所以a•b除以3次c后不能变成1，那么输出No,否则，输出Yes。

代码5（389 ms）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
const int INF=0x3f3f3f3f;
const int N=1e5+5;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ll a,b;
        scanf("%lld %lld",&a,&b);
        ll m=a*b;
        ll v=pow(m,1./3);
        while(v*v*v<m)v++;
        if(v*v*v!=m)
        {
            printf("No
");
        }
        else
        {
            ll g=gcd(a,b);
            for(int i=0;i<3;i++)
            {
                ll c=gcd(g,m);
                m/=c;
            }
            if(m!=1)printf("No
");
            else printf("Yes
");
        }
    }
    return 0;
}