该题目告诉我们两个数\(x,y\)它们的\(\frac{lcm(x, y)}{gcd(x, y)}\)如果是一个完全平方数的话,我们就称它们是相邻的。 现在给我们一个长度为\(n\)的数组\(a\),每一秒数组中的每个元素\(a_i\)都被数组中与当前值相邻的所有元素(包括其自身)的乘积所取代。让\(d_i\)是每一个\(a_i\)的相邻的值,一个数组的美丽度被定义为\(max_{1\leq i \leq n} d_i\)。现在有\(q\)次询问,每次都会让我们求出来\(w\)秒后这个数组的美丽度是多少。
思路:
看到\(\frac{lcm(x,y)}{gcd(x, y)}\)是一个完全平方数,可以想着去推一下式子,因为\(lcm(x, y) = \frac{x * y}{gcd(x, y}\),所以可以将原式推导为\(\frac{x * y}{(gcd(x, y)) ^ {2}}\) 是一个完全平方数,所以可以写成\((\frac{\sqrt{x * y}}{gcd(x, y)}) ^ 2 == x ^ 2\)当且仅当\(x * y\)是完全平方数的时候该等式方才成立。那么问题就转化成了将\(x * y\)分解质因数,其中每一个因子的幂次都可以被\(2\)整除也就是\(x * y = p_{1} ^ {k_1} * p_{2} ^ {k_2} \dots * p_{n} ^ {k_n}\),其中\(k_1,k_2,k_3 \dots k_n\)都是\(2\)的倍数。因此我们只需要记录\(z_i = p_{1} ^ {k_1\%2} * p_{2} ^ {k_2 \% 2} \dots * p_{n} ^ {k_n \% 2}\) ,如果\(z_i == z_j\)说明两数相乘的质因子的幂次都为偶数,是个完全平方数。
用欧拉筛来得到每一个数的最小质因子
void Eular(int n) { prime[idx ++ ] = 2; minp[2] = 2; st[2] = true; for (int i = 3; i <= n; i += 2) { if (!st[i]) prime[idx ++ ] = i, minp[i] = i, st[i] = true; for (int j = 0; prime[j] * i <= n; j ++ ) { st[prime[j] * i] = true; minp[prime[j] * i] = prime[j]; if (i % prime[j] == 0) break; } } }
在我们得到\(z_i\)的时候如果出现了偶数次幂,那么我们后面在判断完全平方数的时候还是会被分解掉,所以我们只需要在出现奇数次幂的时候在\(z_i\)的基础上乘上一个\(p_{i} ^ {1}\)
void solve() { int n; std::cin >> n; std::vector<int> a(n + 1); rep(i, 1, n + 1) std::cin >> a[i]; std::map<int, int> mp; rep(i, 1, n + 1) { int val = a[i]; int z = 1; while (val > 1) { int p = minp[val]; int cnt = 0; while (val % p == 0) { cnt ++; val /= p; } if (cnt % 2 == 1) z *= p; } mp[z] ++; } // 找到匹配上的另一个数 int cnt0 = 0; for (auto &p : mp) cnt0 = std::max(cnt0, p.second); for (auto &p : mp) { if (p.first == 1 || p.second % 2 == 1) continue; mp[1] += p.second; mp[p.first] = 0; } int cnt1 = 0; for (auto &p : mp) cnt1 = std::max(cnt1, p.second); int m; std::cin >> m; while (m -- ) { int op;std::cin >> op; std::cout << (op == 0 ? cnt0 : cnt1) << "\n"; } }