【数论】翻倍
题意
给定两个正整数,初始时两数均为 $1$。
你可以进行任意次(也可以不进行)翻倍操作,每次操作任选一个非负整数 $k$,令两数中的一个数乘以 $k$,另一个数乘以 $k^2$。
请你计算,是否能够通过一系列操作,使得最终第一个数变为 $a$,第二个数变为 $b$。
多组数据,$T = 350000$,$1 \le a, b\le 1e9$
思路
思路1
容易发现只需要考虑 $k$ 是质数的情况即可,且注意到对于同一个 $k$ 来说,可能会被选很多次。假设有 $x$ 次是 $k$ 作用到了第一个数 $a$,$y$ 次是 $k^2$ 作用到了第一个数 $a$,$a$ 最终包含的 $k$ 的幂次为 $cnt1$,$b$ 最终包含的 $k$ 的幂次是 $cnt2$,则需要满足 $x + 2y = cnt1$ 和 $2x + y = cnt2$ 联立后有非负整数解。
根据上面的思路,就可以得到一个做法:对 $a$ 和 $b$ 进行素因数分解,如果二者素因子种类完全相同,则继续考虑每个素因子的次数,使用上面分析的两个方程联立求解,判断解是否为非负整数解。假如所有的素因子求解方程都有非负整数解,则说明可以通过这样的操作达成目标,否则则不可以。
该思路需要预处理出根号值域内的所有素数,然后对每组数据进行素因数分解($O(\frac{\sqrt n}{\ln n})$, 最差是该数是一个比根号值域大的素数,需要遍历 $1$ 到 $\sqrt n$ 之间所有的素因子),并逐个素因子判断是否符合题意,所以时间复杂度为 $O(\frac{T\sqrt n}{\ln n})$,直接代入计算大约是 $5 \times 10^8$ 的计算量,$1$ 秒的时限是明显不够的,如果有 $10$ 秒时限的话或许可以冲一下。
思路2
注意到每次用一个 $k$ 操作之后,会导致 $a$ 和 $b$ 总共被乘了 $k^3$,所以最终 $ab$ 应该是完全立方数,否则无解。
考虑每个素数 $k$,其被用来操作的次数假设是 $cnt$,$a$ 中 $k$ 的次数为 $x$,$b$ 中 $k$ 的次数为 $y$,则满足 $cnt \le x \le 2cnt$,$cnt \le y \le 2cnt$,$x + y = 3cnt$,满足这个就等价于能凑出来。由于 $x \ge cnt$ 时一定有 $y \le 2cnt$,所以其实就是 $x \ge cnt$ 且 $y \ge cnt$。$x \ge cnt$ 等价于 $k^{cnt}$ 能够整除 $a$,而 $cnt = \frac{x+y}{3}$,$x + y$ 为 $ab$ 中 $k$ 的次数,所以 $ab$ 开立方之后 $k$ 的次数就是 $cnt$。由于素数之间互相独立且互素,所以其实就是 $ab$ 开立方之后能够整除 $a$,且能整除 $b$。
综上,只要判断 $ab$ 是不是完全立方数,然后判断 $ab$ 开立方之后能不能整除 $a$ 和 $b$ 即可。
代码
思路1代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = sqrt(1e9 + 7);
int T;
LL a, b;
LL primes[N], idx = 0;
bool st[N];
void getPrimes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[idx++] = i;
}
for (int j = 0; i * primes[j] <= n; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
LL gcd(LL a, LL b) {
return b == 0 ? a : gcd(b, a % b);
}
void getFactors(int x, vector<PII> &factors) {
int r = sqrt(x);
for (int i = 0; i < idx && primes[i] <= x && x != 1; i++) {
if (x % primes[i] == 0) {
int cnt = 0;
while (x % primes[i] == 0) {
x /= primes[i];
cnt++;
}
factors.push_back({primes[i], cnt});
}
}
if (x > 1) {
factors.push_back({x, 1});
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
getPrimes(N - 1);
while (T--) {
cin >> a >> b;
vector<PII> f1, f2;
getFactors(a, f1);
getFactors(b, f2);
// 2 * x + y = cnt1
// x + 2 * y = cnt2
int n1 = f1.size(), n2 = f2.size();
if (n1 != n2) {
cout << "No\n";
} else {
bool ok = true;
for (int i = 0; i < n1; i++) {
int ff1 = f1[i].first, ff2 = f2[i].first;
if (ff1 != ff2) {
ok = false;
break;
}
int cnt1 = f1[i].second, cnt2 = f2[i].second;
if ( (2 * cnt1 - cnt2) % 3 != 0 || (2 * cnt2 - cnt1) % 3 != 0 ) {
ok = false;
break;
}
int x = (2 * cnt1 - cnt2) / 3, y = (2 * cnt2 - cnt1) / 3;
if (x < 0 || y < 0) {
ok = false;
break;
}
}
if (ok) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
return 0;
}
思路2代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = sqrt(1e9 + 7);
int T;
LL a, b;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cin >> a >> b;
LL t = round(pow(a * b, 1.0 / 3));
// LL t = pow(a * b, 1.0 / 3);
// printf("%lld\n", t);
// printf("%lf\n", pow(a * b, 1.0 / 3));
if (t * t * t != a * b) {
puts("No");
} else {
if (a % t == 0 && b % t == 0) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}