题目描述
题目有点难懂,我也读了好久。 给n个数$a_i$,q个询问。$lcm(a_x,a_y)/gcd(a_x,a_y) = z^2$,则称$a_x$与$a_y$ 是adjacent的,对于 相互adjacent 的数一次操作可以使$a_x=a_y=a_x*a_y$。
例如样例二, [12,3,20,5,80,1]。在一次操作:与12 adjacent的元素为{12,3},与3 adjacent的元素为{12,3},与20 adjacent的元素为{20,5,80},与5 adjacent的元素为{20,5,80},与80 adjacent的元素为{20,5,80},与1 adjacent的元素为{1}。一次操作后,数组被转换为[12 * 3 , 12 * 3, 20 * 5 * 8 , 20 * 5 * 8 , 20 * 5 * 8 , 1 ],即[36,36,8000,8000,8000,1]。
q次询问,每次一个w,问w+1(因为从w=0时也有一次操作)次操作后,数组中最多的相互adjacent的个数。
输入
第一行T组数据。
每组数据第一行一个n,第二行n个数$a_i$ 。第二行q,询问次数。接下来q行询问w.
1≤ $\sum$n ≤$3⋅10^5$ , 1≤$a_i$≤$10^6$ , 1≤ $\sum$q ≤$3⋅10^5$ , 0≤w≤$10^{18}$ .
输出
每次询问的数组中最多的相互adjacent的个数。
样例
输入
2
4
6 8 4 2
1
0
6
12 3 20 5 80 1
1
1
输出
2
3
思路
( 分解质因数) $O(nlogn)$
首先,怎么找adjacent数。
对$a_i$ 等价于$a_i$ 消去平方数,以样例二为例[12,3,20,5,80,1],
$[12] = 2 ^2 * 3 = 3,[3] = 3 ,[20] = 2^2 * 5 = 5 , [5] = 5 , [80] = 2^4 *5 = 5 , [1] = 1$ ,
所以等价数组为[3,3,5,5,5,1],相同的数即为相互adjacent的数,分解质因数即可求得。
其次怎么处理询问。
模拟一下,把所有数等价后的数乘起来变成新的a[]数组即可。w>=1的结果和w=1时是不变的,也就是w只有两种情况0或非0。
在q次询问前预处理出,两种情况:w=0时模拟一次,w>0时模拟两次。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Mn=3e5+17;
map<long long,int> mp;
ll b[Mn],a[Mn];
//线性筛
int r[Mn],tail;
bool prim[Mn];
void ol(){
tail=0; prim[0]=prim[1]=true;
for(int i=2;i<Mn;++i){
if(!prim[i]) r[tail++]=i;
for(int j=0;j<tail&&i*r[j]<=Mn;++j){
prim[i*r[j]]=true;
if(!i%r[j]) break;
}
}
}
int main(){
ol();
int T;scanf("%d",&T);
while(T--){
mp.clear();
int n;scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
//分解质因子
for(int i=1;i<=n;++i){
b[i]=1;
for(int j=0;j<tail&&r[j]*r[j]<=a[i];++j){
if(a[i]%r[j]==0){
int cnt=0;
while(a[i]%r[j]==0) a[i]/=r[j],++cnt;
if(cnt&1) b[i]*=r[j];
}
}
if(a[i]!=1) b[i]*=a[i];
//用map记录当前等价数的adjacent个数
mp[b[i]]++;
}
//w=0 情况
int ans1=0;
for(auto x:mp) ans1=max(ans1,x.second);
//w>0 情况
for(int i=1;i<=n;++i) a[i]=((mp[b[i]]&1)!=0)?b[i]:1ll;
mp.clear();
for(int i=1;i<=n;++i) mp[a[i]]++;
int ans2=0;
for(auto x:mp) ans2=max(ans2,x.second);
int q;scanf("%d",&q);
while(q--){
ll w;scanf("%lld",&w);
if(w==0) printf("%d\n",ans1);
else printf("%d\n",ans2);
}
}
}