BOJ 28138 | 재밌는 나머지 연산

전승민·2023년 5월 29일
0

BOJ 기록

목록 보기
62/68

5월 월간 향유회 A번 문제입니다. 나머지 정리를 배웠다면 다음 식을 구성할 수 있습니다.

N=mq+RN = mq + R

따라서 NRN - R이 나누어 떨어지도록 하는 mm을 찾으면 됩니다.

단, RR이 나머지여야 하므로 m>Rm > R 이어야 합니다.

NRN-R의 약수를 구하고, RR보다 큰 약수만 세서 개수를 출력해주면 됩니다.

범위가 (1N10121 \le N \le 10^{12})로 심상치 않으니 약수를 O(N)O(\sqrt{N})에 구해주도록 합시다.

코드

Python3로 해결했습니다.

def solve(N, R):
    ans = 0
    P = N - R
    
    for i in range(1, int(P**(1/2))+1):
        if P % i == 0:
            if i > R : ans += i
            if i*i != P and P//i > R:
                ans += P//i
    return ans
    

N, R = map(int, input().split())
print(solve(N, R))

profile
백준 다이아는 갔는데 기본기가 너무 딸린다

0개의 댓글