| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 737 | 126 | 50 | 10.965% |
양의 정수 $N$이 주어진다.
각 성분이 $N$ 이하인 서로소인 모든 양의 정수쌍 $\left( i,j \right)$에 대해 각 성분의 합의 총합을 계산해 보자! 즉, 아래의 수식 값을 구하면 된다.
\[\sum_{i=1}^{N}\sum_{j=1}^N{\left( i+j \right) I\left\{ \gcd\left( i,j \right) =1 \right\}}\]
$I\left\{ condition \right\}$는 Indicator Function으로, $condition$이 참일 때 1ドル,ドル 거짓일 때 0ドル$을 반환한다.
첫 번째 줄에 정수 $N(1\le N\le 10^{11})$이 주어진다.
첫 번째 줄에 각 성분의 합의 총합, 즉 주어진 수식의 결과를 출력한다. 단, 답이 너무 커질 수 있으므로 답을 10ドル^9+7$로 나눈 나머지를 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $N \le 10^3$ |
| 2 | 11 | $N \le 10^{6}$ |
| 3 | 41 | $N \le 10^{9}$ |
| 4 | 42 | 추가적인 제한 조건 없음 |
1
2
조건을 만족하는 쌍은 $\left(1, 1\right)$이 유일하며, 각 성분의 합의 총합은 2ドル$이다.
3
26
조건을 만족하는 쌍은 $\left(1, 1\right),ドル $\left(1, 2\right),ドル $\left(1, 3\right),ドル $\left(2, 1\right),ドル $\left(2, 3\right),ドル $\left(3, 1\right),ドル $\left(3, 2\right)$으로, 각 성분의 합의 총합은 2ドル + 3 +たす 4 +たす 3 +たす 5 +たす 4 +たす 5 =わ 26$이다.
1000
608612156
1000000
969057749
1000000000
895661967
10000000000
858329187
100000000000
203179384
University > 고려대학교 > MatKor Cup > 제5회 고려대학교 MatKor Cup: 2024 Summer/Fall K번