1 bool isprime[1000]; 2 int prime[100],tot; 3 void pri(int n) 4 { 5     tot = 0; 6     memset(isprime,true,sizeof(isprime)); 7     int i,j; 8     for(i=2;i<=n;i++) 9     {10         if(isprime[i]) prime[++tot] = i;11         for(j=1;j<=tot&&i*prime[j]<=n;j++)12         {13             isprime[i*prime[j]] = false;14             if(i%prime[j]==0) break;15         }16     }17 }

 1 int exgcd(int a,int b,int &x,int &y) 2 { 3     if(!b) 4     { 5         x = 1,y = 0; 6         return a; 7     } 8     int ret = exgcd(b,a%b,x,y); 9     int t = x;10     x = y;11     y = t - a/b * y;12     return ret;13 }