CodeForces 616E(數學規律)

題意:

輸入n, m(1  ≤  n, m  ≤  10^13)，求 n%1 + n%2 + ... + n%m的值.

思路:

n%i = n - n/i(整除)*i;

是以 ∑(i=1, m) n%i 可以轉化為 m*n - ∑(i=1, m) n/i*i;

易知：給定一個i，被n整除得c = n/i，另r = n/c，很容易可以得到n整除i到r範圍内的所有數的值都是相同的，是以我們另i為下界，r為上界。那麼我們求 ∑(i=1, m) n/i*i的時候就可以将它們分成若幹組進行求和，另(n/i)相同的連續一段為一組。是以就可以利用等差數列求和公式對i到r範圍内進行求和然後再乘上(n/i)就得到了這一段的ans，同理，其他段也是如此。

#include <algorithm>
#include <iostream>
#define LL long long
using namespace std;
const LL mod = 1e9+7;
LL n, m, ans, up, sum, r;
int main()
{
	cin >> n >> m;
	ans = (n%mod)*(m%mod)%mod;
	up = min(n, m);	//當n>m時, 隻能求m個模; n<m時, 隻能求n個模 
	sum = 0;
	for(LL i = 1; i <= up; ++i)
	{
		r = min(n/(n/i), up);//如果上界超過up, 縮至up 
		LL a = i+r;	//準備求和公式 
		LL b = r-i+1;
		if(a&1) b /= 2;
		else a /= 2;
		sum = (sum + ((a%mod)*(b%mod)%mod)*(n/i)%mod)%mod;//獲得此段的ans 
		i = r;
	}
	cout << (ans-sum+mod)%mod << endl;//防止mod之後相減變負數 
	return 0;
}
           

繼續加油~