Codeforces Round #426 (Div. 1) A.The Meaningless Game (二分+数学)

题目链接：

http://codeforces.com/problemset/problem/833/A

题意：

给你 (a) 和 (b)，两个人初始化为 (1)。两个人其中一方乘以 (k^2)，另一方就乘以 (k)。问你能不能达到 ((a,b)) 这个最终状态。

题解：

设 (X)， (P) 表示两个乘积的集合。

那么，显然：

(S^{2}*P=a) ------ 1

(S*P^{2}=b) ------ 2

所以：(a*b = S^{3}*P^3)。

那么，(S*P= ^{sqrt[3]{ab}})

假设 (S*P = x).

又由公式 (1，2) 得:

(S = frac{a}{x})

(P = frac{b}{x})

所以，我们只需要检查 (a*b) 是否能完美开立方，以及 (a,b) 能否同时整除 (x)。前者直接二分就可以了。

(cin)会 TLE.....

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
const int mod = 1e9+7;
const ll INF =2e15;

ll cubic_root(ll x)
{
  ll mid = 0;
  ll low = 0 ,high = 1000100;
  while(low <= high) {
     mid = (low + high) >> 1;
    if(mid * mid * mid > x) {
      high = mid - 1;
    }
    else if(mid * mid * mid < x){
      low = mid + 1;
    }
    else {
       break;
    }
  }
  return mid;
}

int main(int argc, char const *argv[]) {

  int n;
  //std::cin >> n;
  scanf("%d", &n);
  for(int i= 0;i < n; i++) {
    ll a,b;
    scanf("%lld%lld",&a,&b);
    //std::cin >> a >> b;
    ll x = cubic_root(a * b);
    if(x * x * x != a * b) {
      std::cout << "No" << '
';
    }
    else if(a % x ==0 && b % x == 0) {
      std::cout << "Yes" << '
';
    }
    else std::cout << "No" << '
';
  }
  return 0;
}