<style>
html, body, .ui-content {
background-image: url(https://truth.bahamut.com.tw/s01/201508/7f0e4bd0e01135c9df434733e0d1544a.JPG);
background-color: #333;
color: #DDD;
}
</style>

###### tags: `Meowmeow Online Judge`

# Sum of Divisors

## Description
Let $σ(n)$ denote the sum of divisors of an integer $n$. For example, $σ(12)=1+2+3+4+6+12=28$.
Your task is to calculate the sum $\Sigma^n_{i=1}σ(i)$ modulo $10^9+7$

## Input
The only input line has an integer $n$.
$1 \leq n \leq 10^{12}$

## Output
Print the the sum $\Sigma^n_{i=1}σ(i)$ modulo $10^9+7$.

## 解題思路
$i$出現的次數是$\lfloor\frac n i\rfloor$，累加$i*\lfloor\frac n i\rfloor$即是答案，但計算每個$i$相當費時
把相同$\lfloor\frac n i\rfloor$和在一起算，只需要算$n$的因數次就好
:::danger
:heavy_exclamation_mark:**注意:** 計算$\frac {a*b} 2 % p$時，不能直接對兩者取餘數，要將除以2改成乘以2的乘法反元素才能對兩者取餘數
:::
### 時間複雜度
$O(\sqrt n)$
詳細證明可以看這篇
https://math.stackexchange.com/questions/1069460/how-many-distinct-values-of-floorn-i-exists-for-i-1-to-n
一個簡易的證明是當head不到根號n時數head，有根號n個，之後數coef，也是根號n個
## Code

#include <iostream>

const long long modulo = 1'000'000'007;
const long long inverse_of_two = 500'000'004;

int main() {
	long long n;
	std::cin >> n;
	long long answer = 0;
	long long head = 1;
	while (head <= n) {
		long long coef = n / head;
		long long tail = n / coef;
		answer += ((((head + tail) % modulo) * ((tail - head + 1) % modulo) % modulo) * inverse_of_two % modulo) * (coef % modulo) % modulo;
		answer %= modulo;
		head = tail + 1;
	}
	std::cout << answer << std::endl;
	return 0;
}