Algorithm Code Book

This is our algorithm codebook. Here we keep all our algorithm and data structure codes for demo purpose.

Sieve

Sieve Template
 1 #define mx 50006
 2 vector <int> prime;
 3
 4 bool vis[mx];
 5
 6 void sieve() {
 7 int x=sqrt((int)mx);
 8 for(int i=3; i<=x; i+=2) {
 9 if(vis[i]==0) {
10 for(int j=i*i; j<mx; j+=2*i)
11 vis[j]=1;
12 }
13 }
14 prime.pb(2);
15 for(int i=3; i<mx; i+=2)
16 if(vis[i]==0)
17 prime.pb(i);
18 }
   

Bitwise Sieve

Bitwise Sieve Template
 1 #define mx 40000000
 2 int marked[M/64 + 2];
 3 vector <int> prime;
 4
 5 #define on(x) (marked[x/64] & (1<<((x%64)/2)))
 6 #define mark(x) marked[x/64] |= (1<<((x%64)/2))
 7
 8 bool isPrime(int num) {
 9 return num > 1 && (num == 2 || ((num & 1) && !on(num)));{
 10 }
 11
 12 void sieve(int n) {
 13 for (int i = 3; i * i < n; i += 2) {
 14 if (!on(i)) {
 15 for (int j = i * i; j <= n; j += i + i) {
 16 mark(j);
 17 }
 18 }
 19 }
 20 prime.push_back(2);
 21 for(int i=3; i<M; i+=2) {
 22 if(isPrime(i))
 23 prime.pb(i);
 24 }
 25 }
   

Segmented Sieve

Segmented Sieve Template
 1 #define mx 100005
 2 vector<int>prime;
 3
 4 bool vis[mx];
 5
 6 void sieve() {
 7 int x=sqrt((int)mx);
 8 for(int i=3; i<=x; i+=2) {
 9 if(vis[i]==0) {
 10 for(int j=i*i; j<mx; j+=2*i)
 11 vis[j]=1;
 12 }
 13 }
 14 prime.pb(2);
 15 for(int i=3; i<mx; i+=2)
 16 if(vis[i]==0)
 17 prime.pb(i);
 18 }
 19
 20
 21 int segmented_sieve(int a, int b) {
 22 memset(vis,0,sizeof vis);
 23 if(b<2) return 0;
 24 if(a<2) a=2;
 25 int xx=sqrt((double)b)+1;
 26 for(ll i=0; i<SZ(prime) && prime[i]<=xx; i++) {
 27 ll j=(a/prime[i]);
 28 if(a%prime[i]!=0) j++;
 29 j*=prime[i];
 30 if(j==prime[i]) j+=prime[i];
 31 for(; j<l=b; j+=prime[i])
 32 vis[j-a]=1;
 33 }
 34 int cnt=0;
 35 for(ll i=a; i<=b; i++)
 36 if(vis[i-a]==0) cnt++;
 37 return cnt;
 38 }

Big Mod

Big Mod Template
 1 inline long long bigmod (long long a, long long p, long long m) {
 2 long long res = 1 % m, x = a % m;
 3 while ( p ) {
 4 if ( p & 1 ) res = ( res * x ) % m;
 5 x = ( x * x ) % m;
 6 p >>= 1;
 7 }
 8 return res;
 9 }