代码

#include<bits/stdc++.h>
using namespace std;
namespace GCD
{
    const int max_val = 1e7;
    const int K = 4e3; // sqrt max_val
    int vis[max_val+10],pri[max_val+10],cnt;
    int fac[max_val+10][3],Gcd[K+10][K+10];
    void prework()
    {
        vis[1]=fac[1][0]=fac[1][1]=fac[1][2]=1;
        for(int i=2;i<=max_val;++i)
        {
            if(!vis[i]) 
            {
                fac[i][0]=fac[i][1]=1;
                fac[i][2]=pri[++cnt]=i;
            }
            for(int j=1;j<=cnt&&1ll*i*pri[j]<=max_val;++j)
            {
                vis[i*pri[j]]=1;
                int val=fac[i][0]*pri[j];
                if(val<fac[i][1])
                {
                    fac[i*pri[j]][0]=val;
                    fac[i*pri[j]][1]=fac[i][1];
                    fac[i*pri[j]][2]=fac[i][2];
                }
                else if(val<fac[i][2])
                {
                    fac[i*pri[j]][0]=fac[i][1];
                    fac[i*pri[j]][1]=val;
                    fac[i*pri[j]][2]=fac[i][2];
                }
                else
                {
                    fac[i*pri[j]][0]=fac[i][1];
                    fac[i*pri[j]][1]=fac[i][2];
                    fac[i*pri[j]][2]=val;
                }
                if(i%pri[j]==0) break;
            }
        }
        for(int i=0;i<=K;++i) 
            Gcd[i][0]=Gcd[0][i]=i;
        for(int i=1;i<=K;++i)
            for(int j=1;j<=i;++j)
                Gcd[i][j]=Gcd[j][i]=Gcd[i-j][j];
    }
    int gcd(int a,int b)
    {
        if(a>max_val||b>max_val) return -1;
        int *x=fac[a],res=1;
        for(int i=0,d;i<3;++i)
        {
            if(x[i]<=K) d=Gcd[x[i]][b%x[i]];
            else d=b%x[i]?1:x[i];
            b/=d,res*=d;
        }
        return res;
    }
}
int gcd(int a,int b)
{
    if(b) while((a%=b)&&(b%=a));
    return a+b;
}
int Rand() { return (rand()<<15)|rand(); }
int Rand(int l,int r) { return Rand()%(r-l+1)+l; }
const int T = 1e7;
int val[T];
int main()
{
    srand(0512); GCD::prework();
    for(int i=0;i<T;++i)
        val[i]=Rand(3e6,1e7);
    int res=0;
    for(int i=1;i<T;++i)
        res^=gcd(val[i],val[i-1]);
    return printf("%d\n",res);
}

评测结果