平方数
https://ac.nowcoder.com/acm/contest/6112/A
直接暴力就行。对于任意x,sqrt(x)*sqrt(x)<x,同时注意,转为int时直接是向下取整,如果sqrt(x)小数后面>5,就需要向上取整;所以判断一下sqrt(x),与sqrt(x)+1那个更近就行了;

#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
相当于找规律;
a[x]^a[i]=k,a[i]^a[i+1]=k a[i+1]^a[y]=k;
可以知道,a[x]=a[i+1],a[i]=a[y](中间有偶数个节点)
所以此时a[x]^a[y]=k;
a[x]^a[i]=k,a[i]^a[y]=k;
可以看出a[x]==a[y],此时数组中还需一个k^a[x](中间有奇数个节点)
如果以上条件不满足,就是-1;
这题卡时间,所以注意尽可能优化;

#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
我赛场上其实是懵逼状态,数论不到家;
gcd(x,y)=gcd(x,y-x);
gcd(x,y,z)=gcd(x,y-x,z-y)
所以可以看出,后面差分是不受+x的影响的;
所以先计算差分数组,找出最大公因数k;

#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);//排序保证d[i]都是大于0的
    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;
}