Description
两个人玩一个游戏，一个游戏有好多轮，开始两个人的分数都为\(1\)，每一轮都会选择一个自然数\(k\)，赢的人的分数会乘\(k^2\)，输的人的分数乘\(k\)，给出两个数，问这两个数能否成为两个人的得分。
Input
第一行是一个整数\(n\)，表示有\(n\)局游戏，接下来\(n\)行，每行两个数\(a\)和\(b\)。\(1 \leqslant n \leqslant 350000\)，\(1 \leqslant a, b \leqslant 10^9\)。
Output
对于每局游戏，如果这两个数能成为两个人可能的得分，输出Yes，否则输出No。
Sample Input
62 475 458 816 16247 9941000000000 1000000
Sample Output
YesYesYesNoNoYes
Solution
一种解法是将\(a\)和\(b\)分界素因子，当\(a\)和\(b\)的素因子种类相同，每一种素因子的总数是\(3\)的倍数，且大的数量不超过小的数量的两倍时，说明\(a\)和\(b\)是一种可能的得分。但有\(350000\)组用例，\(a\)，\(b\)最大为\(10^9\)，这种做法会超时。
上一种方法是分的思想，可以转为考虑合。如果\(a\)，\(b\)是一种可能的得分，把\(a\)赢的轮的\(k\)累乘得到\(k_1\)，\(b\)赢的轮的\(k\)累乘的到\(k_2\)，那么有
\[ a=k_1^2 \cdot k_2 \\ b=k_1 \cdot k_2^2 \]这是一个关于未知数\(k_1\)和\(k_2\)两个未知数的方程组，如果这个方程组有整数解，就说明\(a\)和\(b\)是一种可能的得分。解方程组得
\[ k_1k_2=\sqrt[3]{ab} \\ k_1=\frac{a}{k_1k_2} \\ k_2=\frac{b}{k_1k_2} \] 即若满足- \(k_1k_2=\sqrt[3]{ab}\)为整数
- \(a/ k_1k_2\)能整除
- \(b/ k_1k_2\)能整除
这三个条件，则\(a\)和\(b\)是一种可能的得分。反之不是。
Code
#include#include #include #include using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 1e3 + 10;bool check(ll a, ll b){ if (a == 1 && b == 1) return true; ll kk = round(pow(a * b, 1.0 / 3)); if (kk * kk * kk != a * b) return false; if (a % kk || b % kk) return false; return true;}int main(){ int n; scanf("%d", &n); while (n--) { ll a, b; scanf("%lld%lld", &a, &b); printf("%s\n", check(a, b) ? "Yes" : "No"); } return 0;}