本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 讨论。

显然有以下结论：

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

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

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

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