�ݺ�ߣ

Beyond Problem Solving
2022. 09. 29(목)
18:00 ~ 21:00

https://www.acmicpc.net/problem/5615

area = 2𝑥𝑥𝑥𝑥 + 𝑥𝑥 + 𝑦𝑦
인데 어떤 x,y에 대해서 나올 수 없는 area를 판별하는 문제

area = 2𝑥𝑥 이면
짝수만 가능하고
area = 𝑥𝑥y (x > 1, y > 1)이면
합성수만 가능하고

2 ∗ area + 1 = 2 2𝑥𝑥𝑥𝑥 + 𝑥𝑥 + 𝑦𝑦 + 1
2 ∗ 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 + 1이 소수인지 판단하면 되는 문제!
2 ∗ area + 1 = 4𝑥𝑥𝑥𝑥 + 2𝑥𝑥 + 2𝑦𝑦 + 1
2 ∗ area + 1 = (2𝑥𝑥 + 1)(2𝑦𝑦 + 1)

def is_prime(n):
i = 5
if n % 2 == 0:
return n == 2
if n % 3 == 0:
return n == 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return n != 1
N = int(sys.stdin.readline())
ans = 0
for i in range(N):
s = int(sys.stdin.readline())
if is_prime(s * 2 + 1):
ans += 1
print(ans)
Python
#include<iostream>
using namespace std;
using llu = unsigned long long;
int is_prime(llu n) {
llu i = 5;
if (n % 2 == 0)
return n == 2;
if (n % 3 == 0)
return n == 3;
while (i * i <= n) {
if (n % i == 0)
return 0;
i += 2;
}
return n != 1;
}
int main() {
llu N;
cin >> N;
llu a = 0;
for (int i = 0; i < N; i++) {
llu s;
cin >> s;
if (is_prime(s * 2 + 1))a++;
}
cout << a << endl;
}
C++

페르마의 소정리
p가 소수이고 a가 p의 배수가 아니면 아래의 수식을 만족한다.
𝑎𝑎𝑝𝑝−1𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1
𝑎𝑎𝑝𝑝−1
≡ 1 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝)
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
(≡는 합동으로 양변을 p로 나눈 나머지가 같다는 뜻)
27−1 𝑚𝑚𝑚𝑚𝑚𝑚 7 = 26 𝑚𝑚𝑚𝑚𝑚𝑚 7 = 128 𝑚𝑚𝑚𝑚𝑚𝑚 7 = 1
p를 소수인 7, a를 p의 배수가 아닌 2로 지정한 예시

p가 소수가 아니면(합성수) 만족할 수도 있고 아닐 수도 있다!
391−1
𝑚𝑚𝑚𝑚𝑚𝑚 91 = 1
(7x13=91)
p를 합성수인 91, a를 p의 배수가 아닌 3로 지정한 예시
8727963568087712425891397479476727340041449 𝑚𝑚𝑚𝑚𝑚𝑚 91 = 1

p가 소수가 아니면(합성수) 만족할 수도 있고 아닐 수도 있다!
391−1
𝑚𝑚𝑚𝑚𝑚𝑚 91 = 1
(7x13=91)
p를 합성수인 91, a를 p의 배수가 아닌 3로 지정한 예시
8727963568087712425891397479476727340041449 𝑚𝑚𝑚𝑚𝑚𝑚 91 = 1
소수 p는 위의 식을 만족한다. 그러므로 위 수식을 만족하지 않으면 합성수이다.

빠른 거듭제곱 연산
251
= (22)25 � 2
= (24
)12
� 22
� 2
= (28)6 � 22 � 2
= (216
)3
� 22
� 2
= (232)1 � 216 � 22 � 2
251
를 계산하는데 있어 2를 51번 곱할 필요는 없다.

251
= (22)25 � 2
= (24
)12
� 22
� 2
= (28)6 � 22 � 2
= (216
)3
� 22
� 2
= (232)1 � 216 � 22 � 2
251
지수가 홀수면 밑을 따로 곱하고 밑은 제곱시킨다.
= (4)25� 2
= (16)12
� (4) � 2
= (256)6� (4) � 2
= (65536)3
� (4) � 2
= (4294967296)1� (65536) � (4) � 2

251
= (22)25 � 2
= (24
)12
� 22
� 2
= (28)6 � 22 � 2
= (216
)3
� 22
� 2
= (232)1 � 216 � 22 � 2
251
지수가 홀수면 밑을 따로 곱하고 밑은 제곱시킨다.
= (4)25� 2
= (16)12
� (4) � 2
= (256)6� (4) � 2
= (65536)3
� (4) � 2
= (4294967296)1� (65536) � (4) � 2
def fast_pow(x, y):
ret = 1
while y:
if y % 2 == 1:
ret *= x
y //= 2
x *= x
return ret
Python
llu fast_pow(llu x, llu y) {
llu ret = 1LL;
while (y) {
if (y & 1) {
ret *= x;
}
y /= 2;
x *= x
}
}
C/C++
𝑂𝑂(log 𝑛𝑛)

빠른 거듭제곱 연산을 활용한 빠르고 안전한 나머지 연산
𝑎𝑎 + 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 = ( 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 + (𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐)) 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐
𝑥𝑥𝑦𝑦
𝑚𝑚𝑚𝑚𝑚𝑚 𝑧𝑧를 계산하는데 컴퓨터에서 정수 overflow가 발생하므로 아래와 같이 연산한다.
가능한 모든 변수를 z로 나눈 나머지 값을 사용한다.
def fast_safe_mod(x, y, z):
ret = 1
x %= z
while y:
if y % 2 == 1:
ret = ((ret % z) * (x % z)) % z
y //= 2
x = ((x % z) * (x % z)) % z
return ret
Python
llu fast_safe_mod(llu x, llu y, llu z) {
llu ret = 1LL;
x %= z;
while (y) {
if (y & 1) {
ret = ((ret % z) * (x % z)) % z;
}
y /= 2;
x = ((x % z) * (x % z)) % z;
}
return ret;
}
C/C++
𝑎𝑎 − 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 = ( 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 − (𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐)) 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐
𝑎𝑎 ∗ 𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 = ( 𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐 ∗ (𝑏𝑏 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐)) 𝑚𝑚𝑚𝑚𝑚𝑚 𝑐𝑐
모듈러 연산의 특징

밀러-라빈 소수판별 페르마의 소정리
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1
p가 홀수인 소수라면 p-1은 짝수이고 모든 짝수는 다음과 같이 표현할 수 있다.
2𝑠𝑠
� 𝑑𝑑
따라서, 𝑝𝑝 − 1을 2𝑠𝑠
� 𝑑𝑑 로 치환할 수 있다.
𝑎𝑎2𝑠𝑠�𝑑𝑑
≡ 1 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) 𝑎𝑎2𝑠𝑠�𝑑𝑑
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1 𝑎𝑎2𝑠𝑠�𝑑𝑑
% 𝑝𝑝 = 1
(d는 무조건 홀수)

2𝑠𝑠
� 𝑑𝑑
% 𝑝𝑝 = 1
그러므로 p가 소수이면 위 수식을 어떻게 변형해도 만족해야 한다.
𝑎𝑎2𝑠𝑠�𝑑𝑑 ≡ ±12 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) (양변에 루트를 씌워도 식을 만족해야 한다)
밀러-라빈 소수판별

2𝑠𝑠
� 𝑑𝑑
% 𝑝𝑝 = 1
𝑎𝑎2𝑠𝑠−1�𝑑𝑑
≡ ±12 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) (좌측항은 왼쪽과 같이 표현할 수 있다)
≡ ±12 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝)
𝑎𝑎𝑑𝑑
⋮
P가 정말 소수라면 위의 모든 식에 대하여 만족해야 한다.
합동식

2𝑠𝑠
� 𝑑𝑑
% 𝑝𝑝 = 1
• 1 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1
• −1 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 𝑝𝑝 − 1
≡ ±12 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) (좌측항은 왼쪽과 같이 표현할 수 있다)
𝑎𝑎𝑑𝑑
⋮
P가 정말 소수라면 위의 모든 식에 대하여 만족해야 한다.
계속해서 루트를 씌워나가는데
만약 우측항이 -1이면 더 이상 루트를 씌울 수 없다.
그러므로 가능한 모든 수식을 만족하였으니
소수 일 수 있다!
• break 시점
합동식

2𝑠𝑠 � 𝑑𝑑
따라서, 𝑝𝑝 − 1을 2𝑠𝑠 � 𝑑𝑑 로 치환할 수 있다.
𝑎𝑎2𝑠𝑠�𝑑𝑑 ≡ 1 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) 𝑎𝑎2𝑠𝑠�𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = 1 𝑎𝑎2𝑠𝑠�𝑑𝑑 % 𝑝𝑝 = 1
𝑎𝑎2𝑠𝑠−1�𝑑𝑑 ≡ ±12 (𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝) (좌측항은 왼쪽과 같이 표현할 수 있다)
𝑎𝑎𝑑𝑑
⋮
• break 시점
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 = ±1 𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
𝑎𝑎𝑑𝑑
⋮
합동식에서 우측항이 -1 인것은
일반식에서 우측항이 p-1과 같다.
합동식 일반식

𝑎𝑎𝑑𝑑
⋮
• break 시점
𝑎𝑎𝑑𝑑
⋮
𝑎𝑎𝑑𝑑
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝 즉, 지수항이 홀수가 되어 d만 남게되었을 때,
𝑎𝑎𝑑𝑑
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝가 1이면 소수일 수 있고, 그렇지 않으면 무조건 합성수이다.
• end 시점
합동식 일반식

• break 시점
𝑎𝑎𝑑𝑑
⋮
𝑎𝑎𝑑𝑑
𝑎𝑎𝑑𝑑
• end 시점
𝑟𝑟 = 𝑎𝑎𝑋𝑋
𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝
𝑖𝑖𝑖𝑖 𝑟𝑟 == 𝑝𝑝 − 1
𝑋𝑋 = 𝑝𝑝 − 1
𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 (𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝)
𝑖𝑖𝑖𝑖 𝑋𝑋 𝑖𝑖𝑖𝑖 𝑜𝑜𝑜𝑜𝑜𝑜
𝑖𝑖𝑖𝑖 𝑟𝑟 == 1
𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓 (𝑛𝑛𝑛𝑛𝑛𝑛 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝)
𝑋𝑋 = 𝑋𝑋/2
2𝑆𝑆
� 𝑑𝑑 를 𝑋𝑋라 한다.
일반식 의사 코드

• break 시점
𝑎𝑎𝑑𝑑
⋮
𝑎𝑎𝑑𝑑
𝑎𝑎𝑑𝑑
• end 시점
𝑋𝑋 = 𝑝𝑝 − 1
2𝑆𝑆
일반식 의사 코드
𝑂𝑂(𝑙𝑙𝑙𝑙𝑙𝑙2
𝑛𝑛)

𝑋𝑋 = 𝑝𝑝 − 1
2𝑆𝑆
의사 코드
𝑛𝑛)
• break 시점
𝑎𝑎𝑑𝑑
𝑎𝑎𝑑𝑑
• end 시점
이제 𝑎𝑎를 어떤 숫자로 하는지가 관건이다.
여러가지 𝑎𝑎에 대해서 테스트 한다.
서로 다른 𝑎𝑎를 k번 테스트 하였을 때
합성수가 소수라고 판별될 확률은
1
4𝑘𝑘 이다.

𝑋𝑋 = 𝑝𝑝 − 1
2𝑆𝑆
의사 코드
𝑛𝑛)
• break 시점
𝑎𝑎𝑑𝑑
𝑎𝑎𝑑𝑑
• end 시점
이제 𝑎𝑎를 어떤 숫자로 하는지가 관건이다.
여러가지 𝑎𝑎에 대해서 테스트 한다.
서로 다른 𝑎𝑎를 k번 테스트 하였을 때
합성수가 소수라고 판별될 확률은
1
4𝑘𝑘 이다.
𝑛𝑛 < 341,550,071,728,321일 경우 𝑎𝑎 = 2,3,5,7,11,13,17에 대해서만 검사해보면 충분하다
𝑎𝑎𝑙𝑙𝑙𝑙𝑙𝑙 = [2,7,61]
𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎 𝑖𝑖𝑖𝑖 𝑎𝑎𝑙𝑙𝑙𝑙𝑙𝑙:
𝑖𝑖𝑖𝑖 𝑎𝑎 > 𝑝𝑝
𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡
𝑖𝑖𝑖𝑖 𝑝𝑝 < 2
𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓
𝑂𝑂(𝑘𝑘 � 𝑙𝑙𝑙𝑙𝑙𝑙2
𝑛𝑛)
𝑛𝑛 < 4,759,123,141일 경우 𝑎𝑎 = 2,7,61에 대해서만 검사해보면 충분하다 .

import sys
def fast_safe_mod(x, y, z):
ret = 1
x %= z
while y:
if y % 2 == 1:
ret = ((ret % z) * (x % z)) % z
y //= 2
x = ((x % z) * (x % z)) % z
return ret
def is_probability_prime(p):
if p < 2:
return False
a = [2, 7, 61]
i = 0
while i < len(a) and a[i] < p:
x = p - 1
while True:
r = fast_safe_mod(a[i], x, p)
if r == p - 1:
break
if x % 2 == 1:
if r == 1:
break
else:
return False
x /= 2
i += 1
return True
N = int(sys.stdin.readline())
ans = 0
for i in range(N):
s = int(sys.stdin.readline())
if is_probability_prime(s * 2 + 1):
ans += 1
print(ans)
Python
#include<iostream>
#include<vector>
using namespace std;
llu fast_safe_mod(llu x, llu y, llu z) {
llu ret = 1LL;
x %= z;
while (y) {
if (y & 1) {
ret = ((ret % z) * (x % z)) % z;
}
y /= 2;
x = ((x % z) * (x % z)) % z;
}
return ret;
}
llu is_probability_prime(llu p) {
if (p < 2) {
return false;
}
vector<llu> a = {2, 7, 61};
llu i = 0;
while (i<a.size() && a[i] < p) {
llu s = p - 1;
while (true) {
llu r = fast_safe_mod(a[i], s, p);
if (r == p - 1) break;
if (s & 1) {
if (r == 1)break;
else return false;
}
s >>= 1;
}
i++;
}
return true;
}
int main() {
llu N;
cin >> N;
llu a = 0;
for (int i = 0; i < N; i++) {
llu s;
cin >> s;
if (is_probability_prime(s * 2 + 1))a++;
}
cout << a << endl;
return 0;
}
C++

�ݺ�ߣ

[Miller-Rabin] Detailed explanation of the Miller-Rabin prime number test and slide data on how to implement it

Recommended

More Related Content

Similar to [Miller-Rabin] Detailed explanation of the Miller-Rabin prime number test and slide data on how to implement it (20)

More from Bomm Kim (6)

[Miller-Rabin] Detailed explanation of the Miller-Rabin prime number test and slide data on how to implement it