牛客练习赛66

平方数
https://ac.nowcoder.com/acm/contest/6112/A
直接暴力就行。对于任意ｘ，ｓｑｒｔ（ｘ）＊ｓｑｒｔ（ｘ）＜ｘ，同时注意，转为ｉｎｔ时直接是向下取整，如果ｓｑｒｔ（ｘ）小数后面＞５，就需要向上取整；所以判断一下ｓｑｒｔ（ｘ），与ｓｑｒｔ（ｘ）＋１那个更近就行了；

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

异或图
https://ac.nowcoder.com/acm/contest/6112/B
相当于找规律；
ａ［ｘ］＾ａ［ｉ］＝ｋ，ａ［ｉ］＾ａ［ｉ＋１］＝ｋ　ａ［ｉ＋１］＾ａ［ｙ］＝ｋ；
可以知道，ａ［ｘ］＝ａ［ｉ＋１］，ａ［ｉ］＝ａ［ｙ］（中间有偶数个节点）
所以此时ａ［ｘ］＾ａ［ｙ］＝ｋ；
ａ［ｘ］＾ａ［ｉ］＝ｋ，ａ［ｉ］＾ａ［ｙ］＝ｋ；
可以看出ａ［ｘ］＝＝ａ［ｙ］，此时数组中还需一个ｋ＾ａ［ｘ］（中间有奇数个节点）
如果以上条件不满足，就是－１；
这题卡时间，所以注意尽可能优化；

#include<bits/stdc++.h>
using namespace std;
int a[1001000],b[1000010],n;
unordered_map<int,int> mp;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
int main()
{

    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        a[i]=read();mp[a[i]]++;
    }
    for(int i=1;i<=q;i++)
    {
        int k,x,y;
        k=read(),x=read(),y=read();
        if((a[x]^a[y])==k) printf("%d\n",1);
        else{
           if((a[x]==a[y])&&mp[a[x]^k]) printf("%d\n",2);
           else printf("%d\n",-1);
        }
    }
}

公因子
https://ac.nowcoder.com/acm/contest/6112/C
我赛场上其实是懵逼状态，数论不到家；
ｇｃｄ（ｘ，ｙ）＝ｇｃｄ（ｘ，ｙ－ｘ）；
ｇｃｄ（ｘ，ｙ，ｚ）＝ｇｃｄ（ｘ，ｙ－ｘ，ｚ－ｙ）
所以可以看出，后面差分是不受＋ｘ的影响的；
所以先计算差分数组，找出最大公因数ｋ；

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[1000020],max1=0,d[1000010];
int read()
{
    char ch=getchar();int 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;
}
signed main()
{
    cin>>n;
    int k;
    for(int i=1;i<=n;i++) {
        a[i]=read();
    }
   　sort(a+1,a+1+n);／／排序保证ｄ［ｉ］都是大于０的
    for(int i=1;i<=n;i++)
    d[i]=a[i]-a[i-1];
    k=d[2]; 
    for(int i=3;i<=n;i++)
        k=__gcd(k,d[i]);
    int x;
    if(a[1]<0) x=-a[1]%k;//因为第一个数没有计算gcd，所以如果gcd最大，则只需使第一个数是gcd的倍数
    else x=k-a[1]%k;
    cout<<k<<' '<<x;
}