GGGCCCDDDHARD
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- GGGCCCDDDHARD
- 10000ms
- 8192kb
- 64
- 11 (17%)
-
- 출처
- 분류
문제
어떤 사람이 GGGCCCDDD와 이 문제를 보고 다음과 같은 생각을 했다고 합니다.
GGGCCCDDD문제에서는 루프의 각 변수의 초기값이 1이었지만, gcd(0,N) = gcd(N,0) = N이니까, 각 변수의 초기값을 0으로 시작해도 되지 않을까?
그래서 그는 다음과 같은 루프를 돌려보았습니다.
sum = 0;
for (a1 = 0; a1 <= N; a1++)
for (a2 = 0; a2 <= N; a2++)
// ......
for (aM = 0; aM <= N; aM++)
sum = sum + gcd(a1,gcd(a2,... ,gcd(aM-1,aM))....));
그리고 그는 좀 더 빠르게 sum을 구하는 방법까지 구상해 보았는데 이 방법이 GGGCCCDDD문제와 다를 것이 없다는 것을 깨달았습니다. 그래서 N과 M의 범위를 조금만 더 늘리기로 하였습니다. sum을 구하기 위한 좋은 방법을 찾아주세요!
입력
입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.
각 테스트 케이스에 대해, 한 줄에 정수 N과 M (0 <= N <= 109, 1 <= M <= 109) 이 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 한 줄에 하나씩 답을 출력한다. 단, 답이 매우 클 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.
예제 입력
3 2 2 10 4 100000 100000
예제 출력
11 17255 732485951
노트
N = 10, M = 4 인 경우, 아래처럼 계산해볼 수 있다.
int a, b, c, d, sum = 0;
for (a = 0; a <= 10; a++)
for (b = 0; b <= 10; b++)
for (c = 0; c <= 10; c++)
for (d = 0; d <= 10; d++)
sum = sum + gcd(a, gcd(b, gcd(c,d)));
