a962. 新專輯 - 高中生程式解題系統

內容

給定正整數 $N$ ，請求出 $(N \mod 1 + N \mod 2 + \dots + N \mod N)$ 除以 $10^{9} + 9$ 的餘數。這裡 $a \mod m$ 定義為 $a$ 除以 $m$ 的餘數，即唯一的非負整數 $r$ 滿足 $r < | m |$ 且 $a - r$ 能被 $m$ 整除。

輸入說明

N

$1 \leq N \leq 10^{14}$ 。
$N$ 為整數。

輸出說明

S

$S$ 為一整數，代表 $(N \mod 1 + N \mod 2 + \dots + N \mod N)$ 除以 $10^{9} + 9$ 的餘數。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

範例輸入 #3

100000000000000

範例輸出 #3

45752744

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (5%): 1.0s , <1K
不公開測資點#1 (5%): 1.0s , <1K
不公開測資點#2 (5%): 1.0s , <1K
不公開測資點#3 (5%): 1.0s , <1K
不公開測資點#4 (5%): 1.0s , <1K
不公開測資點#5 (5%): 1.0s , <1K
不公開測資點#6 (5%): 1.0s , <1K
不公開測資點#7 (5%): 1.0s , <1K
不公開測資點#8 (5%): 1.0s , <1K
不公開測資點#9 (5%): 1.0s , <1K
不公開測資點#10 (5%): 1.0s , <1K
不公開測資點#11 (5%): 1.0s , <1K
不公開測資點#12 (5%): 1.0s , <1K
不公開測資點#13 (5%): 1.0s , <1K
不公開測資點#14 (5%): 1.0s , <1K
不公開測資點#15 (5%): 1.0s , <1K
不公開測資點#16 (5%): 1.0s , <1K
不公開測資點#17 (5%): 1.0s , <1K
不公開測資點#18 (5%): 1.0s , <1K
不公開測資點#19 (5%): 1.0s , <1K

提示：

當 $N = 10$ 時，有 $S = 0 + 0 + 1 + 2 + 0 + 4 + 3 + 2 + 1 + 0 = 13$ 。

標籤:

數論模數

出處:

TIOJ 1674 [管理者： xavier13540 (柊四千) ]

編號	身分	題目	主題	人氣	發表日期
40097	xavier13540 (柊四千)	a962	作者提供的解法	197	2024-04-26 16:55