网站建设面试常见问题,机器人少儿编程加盟,千博企业网站,深圳市盐田区建设局网站题意#xff1a;
定义数字 x 和 y 是“相邻”的当且仅当 lcm(x,y)/gcd(x,y) 是一个平方数。 给定一个长度为 n 的数组 a。 每过一秒#xff0c;数组 a 会发生变化#xff1a;ai 会变成数组 a 中与其“相邻”的所有数字的乘积。 定义 di 为数组 a 中与 ai “相邻” 的数字个…题意
定义数字 x 和 y 是“相邻”的当且仅当 lcm(x,y)/gcd(x,y) 是一个平方数。 给定一个长度为 n 的数组 a。 每过一秒数组 a 会发生变化ai 会变成数组 a 中与其“相邻”的所有数字的乘积。 定义 di 为数组 a 中与 ai “相邻” 的数字个数。 定义数组 a 的美丽值为 max1≤i≤ndi 给出 q 个询问每次询问给出当前时间 w问当前数组 a 的美丽值。
题解
参考题解 不会做。。emmm。。。看完题解恍然大悟 题目中w的范围0≤w≤1018,那说明不可能真的一轮一轮进行因为w太大了可能会存在a数组发生优先次变化后答案就固定了 题目所定义的“相邻”经过简化后可得 分母为gcd(x,y)2,分子为x * y为了让整体变成平方数那说明x * y就是平方数根据唯一分解定理任何一个数都可以分解成质因数相乘的形式x * y 为平方数说明x和y对应的质因子的幂次奇偶性是相同的。就比如x可以分解出一个3那么y肯定也要分解出一个3这样才能凑出平方 现在我们对x和y进行处理将x和y中偶数次幂的质因子删除掉只留下奇数次幂的质因子。因为偶数次的本身就是平方数了对题目没有影响有影响的是奇数 处理后的到X和Y如果X Yx * y 就是平方数否则就不是 接下来我们来处理美丽值这个问题 在a数组中没出现次数最多的数字的出现次数就是数组a的美丽值 a数组每轮都是会发生改变的我们前面说了只有X Y时X与Y才是相邻的那么与a[i]相邻的有d[i]个数a[i]就变成了a[i]d[i] 我们接着对处理后的A数组进行质因数删除只保留奇数次幂的质因子 如果d[i]是偶数那么a[i]就变成了1否则还是a[i] 我们发现变成1的数之后再也不会发生改变了相当于固定了而没变成1的数永远都不是1,是它本身 因为没变成1的数说明是奇数个那么与A[i]相邻的数也是奇数个相当于A[i]变化后是A[i]d[i],d[i]为奇数而A[i]d[i]经过质因数删除操作后又得到A[i],所以永远不可能是1 说明变化1次和变化多次的答案是一样的 也就是当w1时我们只需要比较不变化的1的个数和变化1次后1的个数输出最大值就行 变化后1的数量 还未变化时出现次数为偶数的非1的数字 原本1的数量 题目非常巧妙好好揣摩
代码
情况数组时最好不要用memset了特别是大数据。。。。 不然
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1e69;
int prime[maxn],tot,tag[maxn];
void Prime(int N){tag[0]tag[1]1;for(int i2;iN;i){if(tag[i]0)prime[tot]i;for(int j0;jtoti*prime[j]N;j){tag[i*prime[j]]1;if(i%prime[j]0)break;}}
}
int a[maxn],sum[maxn];
vectorintvec;
int main()
{int T;Tread();Prime(1000000);while(T--){vec.clear();int n;nread();int maxx0;//maxx表示出现此处最多的数字的出现次数 int one0;//记录没变化时1的数量 //memset(a,0,sizeof(a));for(int i1;in;i)a[i]read();for(int i1;in;i){int tmp1;//tmp为奇数个质因子的乘积 int j0;while(a[i]prime[j]){int num0;while(a[i]%prime[j]0){num;a[i]/prime[j];}if(num%21)tmptmp*prime[j];//如果该质因数分解除奇数j;if (!tag[a[i]]) {tmp * a[i];break;}}//sum用来处理后有多少数是相同的 vec.push_back(tmp); maxxmax(maxx,sum[tmp]);}int even0;for(int x:vec){if(x!1){if(sum[x]%20)///未变化时出现次数为偶数且非 1 的数字数量even; }else{one;}}for (int v : vec) {sum[v] 0;}int q;qread();while(q--){ll w;scanf(%lld,w);if(w0)printf(%d\n,maxx);else printf(%d\n,max(maxx,oneeven));}}return 0;
}
