RSS Feed

최대공약수와 최소공배수로 제약 받는 리스트

Problem 350

출제 일시 : 2021-08-10 00:10:24

크기 n인 리스트는 자연수 n개의 수열입니다.
몇 개 예를 들면 (2,4,6), (2,6,4), (10,6,15,6), (11) 등 입니다.

리스트의 최대공약수, 또는 gcd는 리스트의 모든 항을 나누는 가장 큰 자연수입니다.
보기: gcd(2,6,4) = 2, gcd(10,6,15,6) = 1 그리고 gcd(11) = 11 입니다.

리스트의 최소공배수, 또는 lcm는 리스트의 모든 항에 나뉘어지는 가장 작은 자연수입니다.
보기: lcm(2,6,4) = 12, lcm(10,6,15,6) = 30 그리고 lcm(11) = 11 입니다.

f(G, L, N)를 gcd ≥ G 이고 lcm ≤ L인 크기 N의 모든 리스트의 개수라고 합시다.
예를 들면 아래와 같습니다:

f(10, 100, 1) = 91.
f(10, 100, 2) = 327.
f(10, 100, 3) = 1135.
f(10, 100, 1000) mod 1014 = 3286053.

f(106, 1012, 1018) mod 1014 값을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.