math - procom @ ウィキ

数学系のメソッド

• ユークリッドの互除法でGCDを求める

  int gcd(int a, int b) {
  	if (b == 0) return a;
  	return gcd(b, a%b);
  }

• 拡張ユークリッドの互除法
  ax+by=gcd(a,b)の解をx,yにしまう
  返り値はgcd(a,b)

  int x, y;
  int extgcd(int a, int b) {
  	int d = a;
  	if (b != 0) {
  		d = extgcd(b, a%b);
  		int temp = y;
  		y = x - (a/b)*y;
  		x = temp;
  	} else {
  		x = 1; y = 0;
  	}
  	return d;
  }

• 素数判定

  boolean isPrime(int n) {
  	if (n < 2) return false;
  	for (int i = 2; i * i <= n; i++)
  		if (n % i == 0) return false;
   
  	return true;
  }

• 平方数判定

  boolean isSquare(int n) {
  	int i = (int)Math.sqrt(n);
  	if (i*i == n) return true;
  	return false;
  }

• 約数の列挙(昇順)

  int[] divisor(int n) {
  	List<Integer> list = new ArrayList<Integer>();
  	for (int i = 1; i * i <= n; i++) {
  		if (n % i == 0) {
  			list.add(i);
  			if (i != n/i) list.add(n/i);
  		}
  	}
  	int[] res = new int[list.size()];
  	for (int i = 0; i < res.length; i++)
  		res[i] = list.get(i);
  	Arrays.sort(res);
  	return res;
  }

• 素因数分解
  map.get(k) = l ならば k^l | n

  Map<Integer, Integer> prime_factor(int n) {
  	Map<Integer, Integer> res = new HashMap<Integer,Integer>();
  	for (int i = 2; i * i <= n; i++) {
  		if (n % i == 0) {
  			int count = 0;
  			 do {
  				count++;
  				n /= i;
  			} while (n % i == 0);
  			res.put(i, count);
  		}
  	}
  	if (n != 1) res.put(n, 1);
  	return res;
  }

• 冪乗の計算(x^n)
  繰り返し2乗法
  modをとる

  int mod_pow(long x, int n) {
  	long res = 1;
  	while (n > 0) {
  		if ((n & 1) == 1) res = (res * x) % mod;
  		x = (x * x) % mod;
  		n >>= 1;
  	}
  	return (int)res;
  }

• modでの逆元

  int mod_inverse(int a) {
  	return mod_pow(a, mod-2);
  }

• 階乗(mod)

  int mod_fact(int n) {
  	long res = 1;
  	for (int i = 2; i <= n; i++)
  		res = (res*i) % mod;
  	return (int)res;
  }

• nCk mod p

  int mod_comb(int n, int k) {
  	if (n < 0 || k < 0 || n < k) return 0;
  	long res = mod_fact(n);
  	res = (res*mod_inverse(mod_fact(k))) % mod;
  	res = (res*mod_inverse(mod_fact(n-k))) % mod;
  	return (int)res;
  }

• nCkの表
  res[k] = nCk mod p

  int[] mod_combtable(int n) {
  	int[] res = new int[n+1];
  	res[0] = 1;
  	for (int i = 1; i <= n; i++) {
  		long a = (long)(n-i+1)*mod_inverse(i)%mod;
  		long b = (long)res[i-1];
  		res[i] = (int)(a*b % mod);
  	}
  	return res;
  }

• nPk mod p

  int mod_perm(int n, int k) {
  	long res = mod_fact(n);
  	res = (res*mod_pow(mod_fact(n-k), mod -2)) % mod;
  	return (int)res;
  }

• 階乗 BigInteger

  BigInteger fact_BI(int n) {
  	BigInteger res = BigInteger.ONE;
  	for (int i = 2; i <= n; i++)
  		res = res.multiply(BigInteger.valueOf(i));
  	return res;
  }

• nCk BigInteger

  BigInteger comb_BI(int n, int k) {
  	BigInteger res = fact_BI(n);
  	res = res.divide(fact_BI(k));
  	res = res.divide(fact_BI(n-k));
  	return res;
  }

• エラトステネスの篩
  n以下の素数の表を返す
  res[i]はi番目(0 base)の素数

  int[] sieve(int n) {
  	boolean[] dp = new boolean[n+1];
  	List<Integer> prime = new ArrayList<Integer>();
  	for (int i = 2; i <= n; i++) {
  		if (dp[i]) continue;
  		prime.add(i);
  		for (int j = i + i; j <= n; j += i) 
  			dp[j] = true;
  	}
   
  	int[] res = new int[prime.size()];
  	int count = 0;
  	for (int num : prime)
  		res[count++] = num;
   
  	return res;
  }

• n以下の素数が何個かを返す

  int sieve_num(int n) {
  	boolean[] dp = new boolean[n+1];
  	int res = 0;
  	for (int i = 2; i <= n; i++) {
  		if (dp[i]) continue;
  		res++;
  		for (int j = i + i; j <= n; j += i)
  			dp[j] = true;
  	}
  	return res;
  }

• 区間篩
  区間[a, b]にある素数の表を返す
  a >= 2で正しく動く

  int[] segment_sieve(int a, int b) {
  	int sqrt_b = (int)Math.sqrt(b);
  	boolean[] is_small_prime = new boolean[sqrt_b+1];
  	boolean[] is_prime = new boolean[b-a+1];
  	is_small_prime[0] = is_small_prime[1] = true;
  	for (int i = 2; i <= sqrt_b; i++) {
  		if (!is_small_prime[i]) {
  			for (int j = i+i; j <= sqrt_b; j += i)
  				is_small_prime[j] = true;
  			for (int j = Math.max(2,(a+i-1)/i)*i; j <= b; j += i)
  				is_prime[j-a] = true;
  		}
  	}
   
  	List<Integer> prime = new ArrayList<Integer>();
  	for (int i = 0; i <= b-a; i++)
  		if (!is_prime[i]) prime.add(i+a);
   
  	int[] res = new int[prime.size()];
  	int count = 0;
  	for (int i : prime)
  		res[count++] = i;
   
  	return res;
  }

• 区間[a, b]にある素数の個数を返す
  a >= 2で正しく動く

  int segment_sieve_num(int a, int b) {
  	int p = 0;
  	int sqrt_b = (int)Math.sqrt(b);
  	boolean[] is_small_prime = new boolean[sqrt_b+1];
  	boolean[] is_prime = new boolean[b-a+1];
  	is_small_prime[0] = is_small_prime[1] = true;
  	for (int i = 2; i <= sqrt_b; i++) {
  		if (!is_small_prime[i]) {
  			for (int j = i+i; j <= sqrt_b; j += i)
  				is_small_prime[j] = true;
  			for (int j = Math.max(2,(a+i-1)/i)*i; j <= b; j += i)
  				is_prime[j-a] = true;
  		}
  	}
   
  	for (boolean f: is_prime)
  		if (!f) p++;
   
  	return p;
  }