5078 : 나머지의 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$1$ 부터 $N$ 까지의 수열 $\{1, 2, \dots, N\}$ 과 $1$ 부터 $N$ 까지의 순열 $P$ 에 대해, $\sum_{i=1}^N (i \pmod{P_i})$ 의 최댓값을 구하십시오.
[제약 조건]
• $1 \le N \le 10^9$
• 입력되는 모든 값은 정수입니다.
[제약 조건]
• $1 \le N \le 10^9$
• 입력되는 모든 값은 정수입니다.
입력 설명
정수 $N$ 이 주어집니다.
출력 설명
나머지의 합의 최댓값을 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
$P = \{2, 3, 1\}$ 일 때 $1\%2 + 2\%3 + 3\%1 = 1 + 2 + 0 = 3$ 입니다. 항상 $i \pmod{i+1} = i$ 가 됨을 이용하십시오.