CF1470B

__vector__ · 2024-02-26 20:44:01 · 个人记录

这个远古时期的 1900 到现在感觉只有 1500 难度了，5min 想出正解。。。。。但是调了 0.5h。

• 显然的结论：如果 x,y 两个数有关联，那么 x 和 y 中每一个质因数在 x,y 的质因数分解中出现次数的奇偶必须相同。

• 以下具体内容用来解释。

考虑一下 \frac{lcm(x,y)}{\gcd(x,y)} 的实际意义是什么。

• lcm(x,y)

  考虑质因数分解 x,y，对于任意一个 x 或 y 中分解出的质因数 k，设 k 在 x 中出现 a 次，在 y 中出现 b 次，那么就将 k^{\max(a,b)} 算进 x,y 的 lcm。

• \gcd(x,y)

  和 lcm 相反，仍然考虑质因数分解 x,y，对于任意一个 x 或 y 中分解出的质因数 k，设 k 在 x 中出现 a 次，在 y 中出现 b 次，那么就将 k^{\min(a,b)} 算进 x,y 的 lcm。

两个数相除，造成的影响是什么呢？
假设 x 除以 y，那么对于每一个 x 中的质数，其在最后的商的质因数中出现次数等于它在 x 中出现次数减去在 y 中出现的次数。

综上，回到第一个问题，\frac{lcm(x,y)}{\gcd(x,y)} 的实际意义是：假设可以分解质因数成这个形式：x = a_1^{c_1}\cdot a_2^{c_2}\cdot a_3^{c_3}\cdots,y = b_1^{d_1}\cdot b_2^{d_2}\cdot b_3^{d_3}\cdots，那么 \frac{lcm(x,y)}{\gcd(x,y)}=a_1^{\max(c_1,d_1)-\min(c_1,d_1)}\cdot a_2^{\max(c_2,d_2)-\min(c_2,d_2)}\cdot a_3^{\max(c_3,d_3)-\min(c_3,d_3)}\cdots

另外，完全平方数的每个质因数在其因式分解中的幂都是偶数。
综上，显然可以证明开头的结论。

另外开头结论又可以推出一个实用的小结论，即两个关联的数的奇数次幂的质因数列表都是相同。

问题是现在也只解决了 O(n) 操作一秒钟内的变化，而题目最多有 10^{18}s，还需要继续挖掘性质。

想一下每个数操作后会发生什么变化。

所有相关联的数进行乘积，相同质因数的次幂会相加。

另外注意，相关联的数的相同质因数的次幂的奇偶都是相同的，而我们只关心幂的奇偶，所有可以再根据 d_i 讨论。

显然有以下结论：

• 对于每个质因数，操作完之后其次幂的奇偶不会改变。
• 每个质因数操作完之后其次幂都变成偶数。

第一秒操作完之后，不难发现所有能改变的数都改了，剩下的数其质因数的次幂无论如何不会再改。

也就是说原题的 10^{18} 秒就是个诈骗，第 1 秒和第 t \gt 1 秒答案是一样的。

只需要算出 0,1 秒的答案。