#include #include #include #include #define abs(x) ((x)>0?(x):-(x)) #define HALFLIMIT 6325 #define LIMIT (HALFLIMIT*HALFLIMIT) #define SUMBOUND (LIMIT*25) //The limitation is 40000000*25 #ifdef WIN32 typedef __int64 longlong; #else typedef long long longlong; #endif #define MAXNUMS 73000000 int not_prime[LIMIT]; int pcount; #define primelist not_prime int data[MAXNUMS][4]; int dcount; int cmpdata(const void *p, const void *q){     const int *pi=(const int *)p;     const int *qi=(const int *)q;     int i;     for(i=0;i<4;i++){         if(pi[i]qi[i])return 1;     }     return 0; } int cmpsd(const void *p, const void *q){     const int *pi=(const int *)p;     const int *qi=(const int *)q;     int i;     for(i=0;i<3;i++){         if(pi[i]qi[i])return 1;     }     return 0; } void pushdata(int X,int Y,int Z,int W) {     int t;     data[dcount][0]=X;     data[dcount][1]=Y;     data[dcount][2]=Z;     data[dcount][3]=W;     dcount++; } class cn{     longlong r,i; public:     cn(longlong r, longlong i){this->r=r;this->i=i;}     cn com()const{cn x(r,-i);return x;}     longlong sqrmod()const{return r*r+i*i;}     longlong rel()const{return r;}     longlong img()const{return i;}     cn operator+(const cn& x)const{cn y(r+x.r,i+x.i);return y;}     cn operator-(const cn& x)const{cn y(r-x.r,i-x.i);return y;}     cn operator*(const cn& x)const{cn y(r*x.r-i*x.i,r*x.i+i*x.r);return y;}     cn div(longlong x)const;     bool iszero()const{return r==0&&i==0;} }; cn cn::div(longlong x)const{     longlong u,v;     u=r%x;     v=i%x;     if(u<0)u+=x;     if(v<0)v+=x;     if(u>x/2)u-=x;     if(v>x/2)v-=x;     u=(r-u)/x;     v=(i-v)/x;     return cn(u,v); } cn round(const cn& x, const cn& y){     cn z=x*y.com();     longlong r=y.sqrmod();     return z.div(r); } int *A, *B; cn factor(const cn& x, const cn& y){     if(x.iszero())return y;     return factor(y-round(y,x)*x,x); } int powmod(longlong a, longlong n, int p){     longlong mul=a%p;     longlong base=1;     while(n){         if(n&1){             base*=mul;             base%=p;         }         mul*=mul;         mul%=p;         n>>=1;     }     return (int)base; } int rm1(int p){     int i;     int t=(p-1)/4;     for(i=2;iSS)return -1;     if(ps->S>qs->S)return 1;     return 0; } int sc; void insert_num(int lindex[MAX_PRIME_COUNT], int step){     cn num(1,0);     int i,j;     int u,v;     for(i=0;i<=step;i++){         cn p(A[pstack[i]],B[pstack[i]]);         cn q=p.com();         for(j=0;j=0;i--){             if((i==odd_index&&lindex[i]==(pindex[i]-1)/2)||                     lindex[i]==pindex[i]){                 lindex[i]=0;                 continue;             }             lindex[i]++;             break;         }     }while(i>=0);     if(count&1){         for(j=1;j<=step;j++){             lindex[j-1]=pindex[j]/2;             odd_index=j;             do{                 insert_num(lindex,step);                 for(i=step;i>=j;i--){                     if((i==odd_index&&lindex[i]==(pindex[i]-1)/2)||                             lindex[i]==pindex[i]){                         lindex[i]=0;                         continue;                     }                     lindex[i]++;                     break;                 }             }while(i>=j);         }     }     qsort(SL,sc,sizeof(SL[0]),cmpsl);     for(i=0;iSL[k].S){                     N=SL[i].S+SL[j].S+SL[k].S;                     if(need4&&(N&1)){                         X=2*N-4*SL[k].S;                         Y=2*N-4*SL[j].S;                         Z=2*N-4*SL[i].S;                         W=prod[step+1]*4-2*N;                         pushdata(X,Y,Z,W);                     }else if(!(N&1)){                         N/=2;                         X=N-SL[k].S;                         Y=N-SL[j].S;                         Z=N-SL[i].S;                         W=prod[step+1]-N;                         pushdata(X,Y,Z,W);                     }                 }                 if(SL[i].S+SL[j].S>SL[k].L&&SL[k].L>SL[k].S){                     N=SL[i].S+SL[j].S+SL[k].L;                     if(need4&&(N&1)){                         X=2*N-4*SL[k].L;                         Y=2*N-4*SL[j].S;                         Z=2*N-4*SL[i].S;                         W=prod[step+1]*4-2*N;                         if(W>Z)                            pushdata(X,Y,Z,W);                     }else if(!(N&1)){                         N/=2;                         X=N-SL[k].L;                         Y=N-SL[j].S;                         Z=N-SL[i].S;                         W=prod[step+1]-N;                         if(W>Z)                            pushdata(X,Y,Z,W);                     }                 }             }         }     } #define SQR(x)  ((x)*(x))     if(need2)for(i=0;is2.S){                     tmp=s1;s1=s2;s2=tmp;                 }                 if(s1.S>s3.S){                     tmp=s1;s1=s3;s3=tmp;                 }                 if(s2.S>s3.S){                     tmp=s2;s2=s3;s3=tmp;                 }                 if(s1.S+s2.S<=s3.S)                     continue;                 N=s1.S+s2.S+s3.S;                 if(need8&&(N&1)){                     X=2*N-4*s3.S;                     Y=2*N-4*s2.S;                     Z=2*N-4*s1.S;                     W=prod[step+1]*8-2*N;                     pushdata(X,Y,Z,W);                 }else if(!(N&1)){                     N/=2;                     X=N-s3.S;                     Y=N-s2.S;                     Z=N-s1.S;                     W=prod[step+1]*2-N;                     pushdata(X,Y,Z,W);                 }                 if(s1.S+s2.S<=s3.L||s3.L==s3.S)                     continue;                 N=s1.S+s2.S+s3.L;                 if(need8&&(N&1)){                     X=2*N-4*s3.L;                     Y=2*N-4*s2.S;                     Z=2*N-4*s1.S;                     W=prod[step+1]*8-2*N;                     if(W>Z)                        pushdata(X,Y,Z,W);                 }else if(!(N&1)){                     N/=2;                     X=N-s3.L;                     Y=N-s2.S;                     Z=N-s1.S;                     W=prod[step+1]*2-N;                     if(W>Z)                         pushdata(X,Y,Z,W);                 }             }         }     } } void enumerate(int step, int start){     int i,j;     for(i=start;i1){             int u;             for(u=2;u*u