C. The Meaningless Game

题意

给你两个数，开始都为1,然后每轮可以任选一个k，一边可以乘以$k$，另一边乘以$k^2$,然后问你最终是否可以得到所给的两个数a,b;

思路

$a×b = t^3$,二分是否存在$t$,如果不存在肯定不可以，如果存在，那么要保证a中有t中所有的因子，b中也是，那么就是$ amodt==0 and bmodt == 0$,因为$t = k1k2...kn$,那么$a$中要么是$k1^2$要么是$k1$,同理$b$

代码

#include<bits/stdc++.h>

#define N 100005

using namespace std;

typedef long long LL;

LL gcd(LL n,LL m);

int main(void)

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        LL a,b;

        scanf("%lld %lld",&a,&b);

        LL c = a*b;

        LL l = 0,r = 1000000;

        LL id;

        while(l <= r)

        {

            LL mid = (l+r)/(LL)2;

            if(mid*mid*mid <= a*b)

            {

                l = mid + 1;

                id = mid;

            }

            else r = mid - 1;

        }

        if(id*id*id != a*b)

        {

            printf("No\n");

        }

        else

        {   //aprintf("%d\n",id);

            if(!(a%id)&&!(b%id))

                printf("Yes\n");

            else printf("No\n");

        }

    }

    return 0;

}

LL gcd(LL n,LL m)

{

    if(m == 0)

        return n;

    else return gcd(m,n%m);

}

巴特西

C. The Meaningless Game

C. The Meaningless Game

题意

思路

代码

最新文章

热门文章