Some useful code snippets

Revision en2, by srinivas_8025, 2017-12-11 08:34:51

These codes have been taken from a blog thread on codeforces.

Euler Totient function

int[] phi = new int[n + 1];
for (int i = 1; i <= n; ++i) {
  phi[i] += i;
  for (int j = 2 * i; j <= n; j += i) {
    phi[j] -= phi[i];
  }
}

Floyd-Warshall

for(int k = 0; k < n; k++)
  for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Iterative implementation of GCD

int gcd(int a,int b){
while (a&&b)a>b?a%=b:b%=a;
return a+b;
}

Recursive implementation of GCD

int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
Tags #code, #tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English srinivas_8025 2017-12-11 08:36:54 52
en2 English srinivas_8025 2017-12-11 08:34:51 80
en1 English srinivas_8025 2017-12-11 08:33:10 631 Initial Revision (published)