数论问题的几个工具函数

包括求最大公约数、指数运算求模、高斯 φ 函数 、模运算乘法逆的几个工具函数：

public class NumberTheoryUtil {// 用于返回结果 使 ax + by = dpublic static class Result {int a;int b;int d;public Result(int a, int b, int d) {this.a = a;this.b = b;this.d = d;}}// 求 x 和 y 的最大公约数 d 以及 a 和 b 使 ax+by=d 且 |a|+|b| 最小public static Result gcd(int x, int y) {if ( x%y == 0 ) {return new Result(0,1,y);} else {Result res = gcd(y,x%y);return new Result(res.b, res.a-res.b*x/y, res.d);}}// 求模 a^p mod npublic static int expmod(int a, int p, int n) {if ( p == 0 ) {return 1;} else if ( p%2 ==0 ) {int m = expmod(a,p/2,n);return (m*m)%n;} else {int m = expmod(a,(p-1)/2, n);return (m*m*a)%n;}}// 求小于等于 n 且与 n 互素的自然数的数目，即高斯函数 φ(n)// phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)public static int phi(int n) {int m = (int)Math.sqrt(n+0.5);int r = n;for ( int i=2; i<=m; i++ ) {if ( n%i == 0 )r = r*(i-1)/i;while (n%i==0) n=n/i;}return r;}// 求即高斯函数 φ(k) k = 1,2,...,npublic static int[] phi2(int n) {int[] phi = new int[n+1];for ( int i=2; i<=n; i++ ) {if ( phi[i] == 0 ) {for ( int j=i; j<=n; j+=i ) {if ( phi[j] == 0 )phi[j] = j;phi[j] = phi[j]*(i-1)/i;}}}return phi;}// 求 模 n 运算下 x 的乘法逆 y 使 xy mod n = 1，-1 表示无乘法逆public static int opposite(int x, int n) {Result res = gcd(x,n);if ( res.d == 1 ) {return (res.a + n)%n;} else {return -1;}}}