定义两个数x和y相邻，则满足lcm(x,y)/gcd(x,y)是一个平方数。
现在给出一个数组a
定义$d_i$为$a_i$的相邻的个数。而所有$d_i$中的最大值是数组的美丽值。
每一秒钟，每个元素$a_i$会变为所有与$a_i$相邻的数（包含自身）的乘积。
现在有q次查询，每次查询都要求第i秒时的美丽值。
">Strange Definition
Strange Definition
Created by LXC on Wed May 17 09:09:21 2023
https://codeforces.com/problemset/problem/1470/B
ranting: 1900
tag: bitmasks, graphs, hashing, math, number theory
题意
定义两个数x和y相邻，则满足lcm(x,y)/gcd(x,y)是一个平方数。
现在给出一个数组a
定义$d_i$为$a_i$的相邻的个数。而所有$d_i$中的最大值是数组的美丽值。
每一秒钟，每个元素$a_i$会变为所有与$a_i$相邻的数（包含自身）的乘积。
现在有q次查询，每次查询都要求第i秒时的美丽值。
题解
根据唯一分解定理，每个正整数都可以分解为质数的乘积。设$p_i$是第$i$个质数。
设$x = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}, y = p_1^{\beta_1}p_2^{\beta_2}\cdots p_n^{\beta_n},$
$lcm(x,y) = p_1^{max(\alpha_1, \beta_1)}p_2^{max(\alpha_2, \beta_2)}\cdots p_n^{max(\alpha_n, \beta_n)}$
$gcd(x,y) = p_1^{min(\alpha_1, \beta_1)}p_2^{min(\alpha_2, \beta_2)}\cdots p_n^{min(\alpha_n, \beta_n)}$
$lcm(x,y)/gcd(x,y) = p_1^{max(\alpha_1, \beta_1)-min(\alpha_1, \beta_1)}p_2^{max(\alpha_2, \beta_2)-min(\alpha_2, \beta_2)}\cdots p_n^{max(\alpha_n, \beta_n)-min(\alpha_n, \beta_n)} = p_1^{|\alpha_1-\beta_1|}p_2^{|\alpha_2-\beta_2|}\cdots p_n^{|\alpha_n-\beta_n|}$
如果$lcm(x,y)/gcd(x,y)$是平方数，则说明x和y对应质因子指数奇偶性相同。即$\alpha_i \equiv \beta_i \pmod 2$
那么我们可以对a数组进行处理，得到数组b。
对于每个$a_i$分解质因数。当同一个质因数出现偶数次则不计入，若$a_i = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$则$b_i = p_1^{\alpha_1\mod 2}p_2^{\alpha_2\mod 2}\cdots p_n^{\alpha_n\mod 2}$。
在0秒的时候，b数组中每个数出现的次数其实就是这个数的相邻的个数。所以b中最大的重复值个数就是0秒时的答案。
那么在非0秒时，b中重复个数为非1的奇数，它们各自相邻的个数不会变化。所以统计重复个数为非1的奇数的最大值mx。对于出现次数为偶数可以全部变为1。所有偶数和1的个数之和与mx的最大值就是答案。
代码
1 |
|