BOJ 28138 | 재밌는 나머지 연산

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

$N = mq + R$

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

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

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

범위가 ($1 \le N \le 10^{12}$)로 심상치 않으니 약수를 $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))