C. The Meaningless Game

題目鏈接

題意

給你兩個(gè)數(shù)，開始都為1,然后每輪可以任選一個(gè)k，一邊可以乘以\(k\)，另一邊乘以\(k^2\),然后問你最終是否可以得到所給的兩個(gè)數(shù)a,b;

思路

\(a×b = t^3\),二分是否存在\(t\),如果不存在肯定不可以，如果存在，那么要保證a中有t中所有的因子，b中也是，那么就是$ amodt==0 and bmodt == 0\(,因?yàn)閈)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); }

轉(zhuǎn)載于:https://www.cnblogs.com/zzuli2sjy/p/7266051.html

總結(jié)

以上是生活随笔為你收集整理的C. The Meaningless Game的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。