【题解】牛客练习赛66前三题（包括D的云算法）

首先严厉谴责一下卡输入卡常的操作，B题4e6的输入就离谱，连scanf都被卡了一次（后面同样代码又过了）

A

签到题。我因为手速快也抢到了一血（
题意：输入 ，输出离 最近的完全平方数。
思路：直接用sqrt模拟就过了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n,t,i,j,k;
    cin>>n;
    ll x=sqrt(n);
    if(abs(x*x-n)>abs((x+1)*(x+1)-n)){
        cout<<(x+1)*(x+1);
    }
    else cout<<x*x;
}

B

题面看似很复杂，其实整理出来就是这样：
给一个数组。之后每次询问两个数的异或是否为 或者是否相等。注意如果相等的话要特判一下数组中是否存在这两个数的异或（桥梁），能走两步走到。
以下为第一次TLE，第二次ac的代码（scanf被卡常），需要换快读和puts输出才能做到稳过。万恶的4e6输入QwQ

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[2222222],tong[2222222];
int main(){
    ll n,t,i,j,k,x,y;
    cin>>n>>t;
    for(i=0;i<n;i++)scanf("%lld",&a[i]),tong[a[i]]=1;;
    while(t--){
        scanf("%lld%lld%lld",&k,&x,&y);
        //cin>>k>>x>>y;
        x--,y--;
        //cout<<a[x]<<" "<<a[y]<<endl;
        if(a[x]==a[y]&&tong[a[x]^k])printf("2\n");
        else if((a[x]^a[y])==k)printf("1\n");
        else printf("-1\n");
    }
}

C

给一个数组，问每个数都加上 之后的gcd最大值，以及对应的 的值。
思路：观察到每个数差分之后的数组和 就无关了，而显然加了 之后的数组、差分并不会让gcd变得更小。因此可以先求出差分数组的gcd，然后使得每个数加上 之后是这个gcd的倍数即可。
（这道题wa了6次，原因是用了int的快读模板而不自知，到最后一次wa才发现这个问题）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read()
{
    char ch=getchar();ll x=0,f=1;
    while(ch<'0' || ch>'9')   {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll gcd(ll x,ll y){
    if(y==0)return x;
    return x%y==0?y:gcd(y,x%y);
}
ll a[2222222],tong[2222222];
int main(){
    ll n,t,i,j,k,x,y;
    n=read();
    for(i=0;i<n;i++)a[i]=read();
    for(i=0;i<n-1;i++){
        tong[i]=abs(a[i+1]-a[i]);
    }
    ll g;
    for(i=0;i<n-1;i++)if(tong[i]!=0)break;
    g=abs(tong[i]);

    for(;i<n-1;i++){
       // cout<<g<<endl;
        g=abs(gcd(g,tong[i]));
    }
    g=abs(g);
    cout<<g<<" "<<(g-a[0]%g)%g;
}

D（云算法）

可以发现，对每个数 而言， 的循环节一定是 ，而最终要求每个数的循环节为质数的幂的形式（即只含一种素因子），相当于要求找到一个数，至少包含除了这个素因子以外其他所有的数。
那么我们可以换个思路，对于每个数，枚举其中的某个因子（需要留下来），最后把所有数留下来的素因子的幂做一个lcm，让这个lcm尽可能大就可以了。但怎么解决这个问题我还没找到合适的算法，如果dfs暴力的话复杂度是不够的，所以期待大佬们的其他算法/思路。