[51nod 1225] 余数之和

求. (2≤n≤10^12) bzoj 1257 类似, 但是本题数据更大. 证了一下段数的结论. 去年NOI导刊培训听到这样一个知识点: K/i关于i的分段性, 并举了本题的例子. 一直未领悟, 直到做了[POI 2014] Solor Panels. 现在假装领悟, 并把这道题写一下.

的取值只有个, 枚举, 算出的范围, 是连续的一段, 可使用等差数列求和公式. 注意乘法可能溢出.

证明待填. 马老师口胡了一个, 我觉得一点也不靠谱......网上都说的是可以证明. 奥妙重重......

UPDATE: 证明其实很简单......和CF某题差不多. 至少有一个不超过. 如果, 显然至多有个; 如果......当然至多有个.

学以致用很重要......瞥了一眼WC2016莫比乌斯反演的课件才醒悟.

设, 则是满足条件的最大的数.

#define MOD(x) ((x)%M)
typedef long long ll;
const int M = 1e9 + 7, H = 5e8 + 4;

int main()
{
	ll n;
	scanf("%lld", &n);
	ll ans = MOD(n) * MOD(n) % M;

	for (ll i = 1, j; i <= n; i = j+1) {
		j = n / (n/i);
		ans -= MOD(i + j) * MOD(j - i + 1) % M * H % M * (n/i) % M;
		(ans += M) %= M;
	}

	printf("%lld\n", ans);

	return 0;	
}