백준/백준-C++
수학 및 논리 퍼즐
Beabletoet
2017. 9. 13. 15:23
소수
모든 자연수는 소수의 곱으로 나타낼 수 있다.
x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * 11^j4 * 13^j5 * 17^j6 …
--
소수의 가분성(divisibility)
x = 2^j0 * 3^j1 * 5^j2 * 7^j3 * 11^j4 * 13^j5 * 17^j6 …
y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * 11^k4 * 13^k5 * 17^k6 …
gcd = greatest common divisor = 최대공약수
gcd(x,y) = 2^min(j0,k0) * 3^min(j1,k1) * 5^min(j2,k2) ...
lcm = least common multiple = 최소공배수
lcm(x,y) = 2^max(j0,k0) * 3^max(j1,k1) * 5^max(j2,k2) ...
gcd(x,y)*lcm(x,y) = x*y
--
소수판별
에라토스테네스의 체 (max는 따로 define함)
1 2 3 4 5 6 7 8 9 10 | void eratosthenes(bool *num) { fill(&num[0],&num[max],1); for (int i = 4; i <= max; i += 2) num[i] = 0; for (int i = 3; i*i <= max; i += 2) if (num[i] == 1) for (int j = i*i; j <= max; j += 2 * i) num[j] = 0; } | cs |
--
A∩B의 확률
P(A∩B) = P(B|A)P(A) = (P(B∩A)/P(A))*P(A)
--
A∪B의 확률
P(A∪B) = P(A)+P(B)-P(A∩B)