长沙做网站公,电影采集网站流量,wordpress 图片灯箱,系统优化软件推荐传送门
题意#xff1a; 定义相邻数为lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)是一个平方数#xff0c;则xxx和yyy是相邻的。现在给出q个询问#xff0c;每次询问一个iii#xff0c;表示询问第iii秒后max1indimax_{1in}d_imax1i…传送门
题意 定义相邻数为lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)是一个平方数则xxx和yyy是相邻的。现在给出q个询问每次询问一个iii表示询问第iii秒后max1indimax_{1in}d_imax1indidid_idi表示与aia_iai为相邻数的个数。注意每一秒数组都会改变成与aia_iai是相邻数的乘积。
思路 先考虑怎么化简lcm(x,y)gcd(x,y)\frac{lcm(x,y)}{gcd(x,y)}gcd(x,y)lcm(x,y)我们知道lcm(x,y)x∗ygcd(x,y)lcm(x,y)\frac{x*y}{gcd(x,y)}lcm(x,y)gcd(x,y)x∗y带入得x∗ygcd(x,y)2\frac{x*y}{gcd(x,y)^2}gcd(x,y)2x∗y继续化简(x∗ygcd(x,y))2(\frac{\sqrt{x*y}}{gcd(x,y)})^2(gcd(x,y)x∗y)2所以我们可以知道如果两个数是相邻的那么他们乘积一定是完全平方数。我们需要知道完全平方数有什么特点显然他们的质因子的幂数都是偶数那么两个数相乘为平方数需要满足什么条件呢也比较容易想到他们的质因子幂数相加为偶数那么我们如果在乘之前就把他们的质因子的幂数模2得到两个新的数这两个新数必须相等的时候乘起来才能是平方数。那么这就比较显然了我们可以用mp[i]mp[i]mp[i]表示iii出现的次数第0秒的时候只需要取一个maxmaxmax即可。考虑第零秒到第二秒什么变了什么没变。我们下面把相等的数的集合称为一个团且以下的数的质因子幂数默认是模2意义下的。 如果一个团的数量为偶数那么把他们乘起来之后他们的质因数的幂数都为偶数就变成1了。如果一个团的数量为奇数乘起来之后的质因数的幂数仍为奇数。让后特殊处理下1的情况就好啦。可以发现从第1秒之后他们的数量不会变只需要先得到第零秒的再得到偶数变乘1的数量让后加上原来1的数量与第零秒取maxmaxmax即可。 让后分解质因子肯定不能n\sqrt{n}n分解这里可以记一下每个数的最小质因数让后lognlognlogn分解即可。
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N2000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int prime[N],cnt;
int com[N];
bool st[N];
mapint,intmp;void get_prime(int n)
{for(int i2;in;i){if(!st[i]) prime[cnt]i,com[i]i;for(int j0;prime[j]n/i;j){st[prime[j]*i]true;com[prime[j]*i]min(com[prime[j]*i],prime[j]);if(i%prime[j]0) break;}}
}void divide(int x)
{mapint,inthas;while(x!1){has[com[x]];x/com[x];}int ans1;for(auto x:has) if(x.Y%21) ans*x.X;mp[ans];
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);memset(com,0x3f,sizeof(com));get_prime(1000000);int _; scanf(%d,_);while(_--){scanf(%d,n); mp.clear();for(int i1;in;i){int x; scanf(%d,x);divide(x);}int ans1,ans2; ans1ans20;for(auto x:mp){ans1max(ans1,x.Y);if(x.X1) ans2x.Y;else if(x.Y%20) ans2x.Y;}int q; scanf(%d,q);while(q--){LL op; scanf(%lld,op);if(op0) printf(%d\n,ans1);else printf(%d\n,max(ans1,ans2));}}return 0;
}
/**/
