#782. #6052. 「雅礼集训 2017 Day11」DIV

#6052. 「雅礼集训 2017 Day11」DIV

题目描述

定义复数 a+bia + bi 为整数 kk 的约数,当且仅当 aa 和 bb 为整数且存在整数 cc 和 dd 满足 (a+bi)(c+di)=k(a + bi)(c + di) = k,给定 nn,求出 11 到 nn 的所有满足 a>0a \gt 0 的约数 a+bia + bi 的 aa 的和。答案模 10045358091004535809 输出。

输入格式

一行一个整数 nn。

输出格式

一行一个整数表示答案。

5
35
1000
1752541
1000000
636408476

数据范围与提示

测试点 nn
1 ≤10\leq 10
2 ≤100\leq 100
3 ≤200\leq 200
4 ≤300\leq 300
5 ≤400\leq 400
6 ≤500\leq 500
7 ≤3000\leq 3000
8 ≤5000\leq 5000
9 ≤3×106\leq 3 \times 10 ^ 6
10 ≤5×106\leq 5 \times 10 ^ 6
11 ≤7×106\leq 7 \times 10 ^ 6
12 ≤107\leq 10 ^ 7
13 ≤3×108\leq 3 \times 10 ^ 8
14 ≤5×108\leq 5 \times 10 ^ 8
15 ≤7×108\leq 7 \times 10 ^ 8
16 ≤109\leq 10 ^ 9
17 ≤3×109\leq 3 \times 10 ^ 9
18 ≤5×109\leq 5 \times 10 ^ 9
19 ≤7×109\leq 7 \times 10 ^ 9
20 ≤1010\leq 10 ^ {10}