실버~골드 쪽에서 문제를 풀다보면 가끔 보이는 모듈러 연산이다.
모듈러 연산은 공식만 봤을때 정말 간단하다.

A mod B = A % B

그냥 별거 없다. A를 B로 나눴을때의 나머지를 구하라는 거다.
그럼 빠르게 문제부터 보자.

가짜소수

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 1591 658 525 46.012%
문제
페르마의 소정리 (Fermat's little theorem)의 내용은 다음과 같다.

p가 소수일 때, 임의의 정수 a>1에 대해서, a^p == a (mod p)가 성립한다.

즉, a를 p제곱한 뒤, p로 나눴을 때, 나머지는 a가 되는 것이다.

하지만, p가 소수가 아닌 경우에 어떤 정수 a에 대해서 위의 식을 만족하는 경우가 있다. 이때, p를 밑이 a인 가짜소수라고 한다. (모든 a에 대해서 식을 만족하는 수를 카마이클 수라고 한다)

p와 a가 주어졌을 때, p가 밑이 a인 가짜소수인지 아닌지 알아내는 프로그램을 작성하시오.

입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p)

출력
각 테스트 케이스에 대해서, p가 밑이 a인 가짜소수라면 yes를, 아니라면 no를 한 줄에 하나씩 출력한다.

문제를 봐도 간단하다.
그냥 a^p%p == a 가 되는 수를 찾으라는 거다.
이 문제를 해결하기 위한 핵심 로직은 다음과 같다.

• mod 연산은 그냥 말 그대로 수식으로 집어넣으면 된다.
• 단, 연산의 오버헤드/오버플로우를 조심하면 된다.
• 이 문제의 경우 소수 판별에 필요한 오버헤드도 조심하면 된다.

무슨 뜻인지는 코드를 보며 말하자.

def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True


while True:
    p, a = map(int, input().split())
    
    if a == 0 and p == 0:
        break
    
    cal = 1
    dup = a
    upper = p
    
    while True:
        if upper % 2 == 1:
            cal *= dup
            cal %= p
        
        upper = upper // 2
        if upper == 0:
            break
        dup = dup * dup
        dup %= p 
    
    print('p, a =', p, a)
    if cal % p == a:

        
        if not is_prime(p):
            print('yes')
        else:
            print('no')
    else:
        print('no')

실제 풀이 코드이다.
위에서 말한 2번, 3번 주의점은 다음과 같다.

• 단, 연산의 오버헤드/오버플로우를 조심하면 된다.

        if upper % 2 == 1:
            cal *= dup
            cal %= p
        
        upper = upper // 2
        if upper == 0:
            break
        dup = dup * dup
        dup %= p 

이 코드를 보면 cal% = p , dup% = p 라는 코드로 cal, dup의 크기를 제한해 주는 것을 확인할 수 있다.

왜 이게 되는걸까?

우리가 원하는 답은 다음과 같다.

if cal % p == a:

그러니 여기서 cal을 XY 형식으로 바꿔도 되지 않을까?
그렇기 때문에 위의 계산식은 cal을 Xp 형태로 생각한것이고,
연산 도중에 p를 미리 나눠줌으로써 X만 남겨두는 것이다.

연산의 숫자가 기하급수적으로 커지기 때문에 오버헤드/오버플로우를 미리 방지하는 것이다.

이제 3번째 포인트를 생각해보자.

• 이 문제의 경우 소수 판별에 필요한 오버헤드도 조심하면 된다.

코드를 보면서 설명하겠다.

    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6

소수 판별부분에 위와 같은 코드가 나온다.
여기서 중요하게 봐야할것은

    while i * i <= n:

이 부분이다.

하나 생각해보자. 두수의 크기 차가 가장 적으면서, 그 수의 곱으로 원하는 수를 만들려면 어떻게 해야할까?

말이 좀 이상하게 됐는데, XY = Z가 될때, X , Y 의 크기차를 최소로 줄이는 방법은?

바로 X , Y = Z**0.5 가 되면 될 것이다.
그러니까, 루트를 씌우면 된다는 소리다.

이 말이 이해가 안된다면 좀 더 곰곰히 생각해 보도록 하자.

어쨌든 위와 같은 방식으로 Z가 10만 정도 되는 수라고 한다면
연산량은 10만 -> 317번으로 급감하게 된다.(100000**0.5 = 316.227)

이렇게 하면 오버헤드를 잡을 수 있다.

잡담

플레티넘에 오고 나니 골드급 문제를 풀어도 점수가 오르지 않는다.
골드2짜리 풀어도 2점밖에 안주고 골드4 이하는 점수를 주지 않는다..

이사도 끝났겠다 빨리 자소서를 쓰고 알고리즘을 편하게 풀고싶다..
코테를 위한 알고리즘이 아니라 취미로 해서 그런건지는 몰라도 점수랑 등급에 신경이 쓰이는건 어쩔 수 없나보다.