#6052. 「雅礼集训 2017 Day11」DIV
题目描述
定义复数 a+bi a + bi a+bi 为整数 k k k 的约数，当且仅当 a a a 和 b b b 为整数且存在整数 c c c 和 d d d 满足 (a+bi)(c+di)=k (a + bi)(c + di) = k (a+bi)(c+di)=k，给定 n n n，求出 1 1 1 到 n n n 的所有满足 a>0 a > 0 a>0 的约数 a+bi a + bi a+bi 的 a a a 的和。答案模 1004535809 1004535809 1004535809 输出。
输入格式
一行一个整数 n n n。
输出格式
一行一个整数表示答案。
样例
样例输入 1
5样例输出 1
35样例输入 2
1000样例输出 2
1752541样例输入 3
1000000样例输出 3
636408476数据范围与提示
| 测试点 | n n n |
|---|---|
| 1 | ≤10 \leq 10 ≤10 |
| 2 | ≤100 \leq 100 ≤100 |
| 3 | ≤200 \leq 200 ≤200 |
| 4 | ≤300 \leq 300 ≤300 |
| 5 | ≤400 \leq 400 ≤400 |
| 6 | ≤500 \leq 500 ≤500 |
| 7 | ≤3000 \leq 3000 ≤3000 |
| 8 | ≤5000 \leq 5000 ≤5000 |
| 9 | ≤3×106 \leq 3 \times 10 ^ 6 ≤3×106 |
| 10 | ≤5×106 \leq 5 \times 10 ^ 6 ≤5×106 |
| 11 | ≤7×106 \leq 7 \times 10 ^ 6 ≤7×106 |
| 12 | ≤107 \leq 10 ^ 7 ≤107 |
| 13 | ≤3×108 \leq 3 \times 10 ^ 8 ≤3×108 |
| 14 | ≤5×108 \leq 5 \times 10 ^ 8 ≤5×108 |
| 15 | ≤7×108 \leq 7 \times 10 ^ 8 ≤7×108 |
| 16 | ≤109 \leq 10 ^ 9 ≤109 |
| 17 | ≤3×109 \leq 3 \times 10 ^ 9 ≤3×109 |
| 18 | ≤5×109 \leq 5 \times 10 ^ 9 ≤5×109 |
| 19 | ≤7×109 \leq 7 \times 10 ^ 9 ≤7×109 |
| 20 | ≤1010 \leq 10 ^ {10} ≤1010 |