math


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

数学系のメソッド

  • ユークリッドの互除法で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;
    }
  • 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;
    }