題意：

定義數字 x 和 y 是“相鄰”的當且僅當 lcm(x,y)/gcd(x,y) 是一個平方數。
給定一個長度為 n 的數組 a。
每過一秒，數組 a 會發生變化：ai 會變成數組 a 中與其“相鄰”的所有數字的乘積。
定義 di 為數組 a 中與 ai “相鄰” 的數字個數。
定義數組 a 的美麗值為 max_1≤i≤ndi
給出 q 個詢問，每次詢問給出當前時間 w，問當前數組 a 的美麗值。

題解：

參考題解
不會做。。emmm。。?？赐觐}解恍然大悟
題目中w的范圍0≤w≤10¹⁸,那說明不可能真的一輪一輪進行，因為w太大了，可能會存在a數組發生優先次變化后，答案就固定了
題目所定義的“相鄰”經過簡化后可得

分母為（gcd(x,y)）²,分子為x * y，為了讓整體變成平方數，那說明x * y就是平方數，根據唯一分解定理，任何一個數都可以分解成質因數相乘的形式，x * y 為平方數，說明x和y對應的質因子的冪次奇偶性是相同的。（就比如x可以分解出一個3，那么y肯定也要分解出一個3，這樣才能湊出平方）
現在我們對x和y進行處理，將x和y中偶數次冪的質因子刪除掉，只留下奇數次冪的質因子。（因為偶數次的本身就是平方數了，對題目沒有影響，有影響的是奇數）
處理后的到X和Y，如果X = = Y，x * 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次和變化多次的答案是一樣的
也就是當w>=1時，我們只需要比較不變化的1的個數和變化1次后1的個數，輸出最大值就行
變化后1的數量 = 還未變化時出現次數為偶數的非1的數字 + 原本1的數量
題目非常巧妙，好好揣摩

代碼：

情況數組時最好不要用memset了，特別是大數據。。。。
不然

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e6+9; int prime[maxn],tot,tag[maxn]; void Prime(int N){tag[0]=tag[1]=1;for(int i=2;i<=N;i++){if(tag[i]==0)prime[tot++]=i;for(int j=0;j<tot&&i*prime[j]<N;j++){tag[i*prime[j]]=1;if(i%prime[j]==0)break;}} } int a[maxn],sum[maxn]; vector<int>vec; int main() {int T;T=read();Prime(1000000);while(T--){vec.clear();int n;n=read();int maxx=0;//maxx表示出現此處最多的數字的出現次數 int one=0;//記錄沒變化時1的數量 //memset(a,0,sizeof(a));for(int i=1;i<=n;i++)a[i]=read();for(int i=1;i<=n;i++){int tmp=1;//tmp為奇數個質因子的乘積 int j=0;while(a[i]>=prime[j]){int num=0;while(a[i]%prime[j]==0){num++;a[i]/=prime[j];}if(num%2==1)tmp=tmp*prime[j];//如果該質因數分解除奇數j++;if (!tag[a[i]]) {tmp *= a[i];break;}}//sum用來處理后，有多少數是相同的 vec.push_back(tmp); maxx=max(maxx,++sum[tmp]);}int even=0;for(int x:vec){if(x!=1){if(sum[x]%2==0)///未變化時出現次數為偶數且非 1 的數字數量even++; }else{one++;}}for (int v : vec) {sum[v] = 0;}int q;q=read();while(q--){ll w;scanf("%lld",&w);if(w==0)printf("%d\n",maxx);else printf("%d\n",max(maxx,one+even));}}return 0; }

總結

以上是生活随笔為你收集整理的Strange Definition CodeForces - 1471D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。