题意

定义 $f(i)$ 为非 $i$ 因子的最小正整数，现给出正整数 $n$ ，求 $\sum_{i=1}^nf(i)$ 对 $10^9+7$ 取模后的值。

$n\leq10^{16}$ 。

题解

傻逼题。枚举每个 $f(i)$ 的贡献即可。要容斥掉已经统计的部分。复杂度大概 $\mathcal{O}(1)$ 。

代码

const int N = 1, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll n, ans;
	ll pri[18] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 49, 53, 59};
	int cnt[18];
	int main () {
		for (int t = Read(); t--; ) {
			n = Read(); ans = 0;
			for (int i = 1; i <= 14; i++) cnt[i] = 0;
			for (int i = 2; i <= 59; i++) {
				ll cur = i;
				for (int j = 1; j <= 17; j++) {
					for (int k = 1; k <= cnt[j] && cur % pri[j] == 0; k++, cur /= pri[j]);
					if (cur % pri[j] == 0) {
						cnt[j]++;
						cur = pri[j];
						break;
					}
				}
				ll g = i;
				(ans += (n / cur * (cur - 1) + n % cur) * g % mod) %= mod;
				n /= cur;
			}
			printf ("%lld\n", ans); putchar(10);
		}
		return 0;
	}
}

int main () {
	//freopen("math.in", "r", stdin);
	//freopen("math.out", "w", stdout);
	Main::main();
	return 0;
}