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); }