「math」の編集履歴（バックアップ）一覧はこちら

「math」(2013/10/03 (木) 14:15:20) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

数学系のメソッド

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

数学系のメソッド

-ユークリッドの互除法でGCDを求める
#highlight(java){{
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)
#highlight(java){{
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;
}
}}

-素数判定
#highlight(java){{
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;
}
}}

-平方数判定
#highlight(java){{
boolean isSquare(int n) {
	int i = (int)Math.sqrt(n);
	if (i*i == n) return true;
	return false;
}
}}

-約数の列挙(昇順)
#highlight(java){{
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
#highlight(java){{
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をとる
#highlight(java){{
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での逆元
#highlight(java){{
int mod_inverse(int a) {
	return mod_pow(a, mod-2);
}
}}

-階乗(mod)
#highlight(java){{
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
#highlight(java){{
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
#highlight(java){{
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
#highlight(java){{
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
#highlight(java){{
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
#highlight(java){{
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)の素数
#highlight(java){{
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以下の素数が何個かを返す
#highlight(java){{
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で正しく動く
#highlight(java){{
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で正しく動く
#highlight(java){{
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;
}
}}