HDU2620：數論+分塊

HDU2620

題解

Σ1<=i<=n(k mod i)

k mod i = k - (k/i)*i

Σ1<=i<=n(k mod i)

 = Σ1<=i<=n[k - (k/i)*i]

 = nk - Σ1<=i<=n (k/i)*i

 存在一段區間的k/i相同，隻要求出數量。

設k / i = k / j = d，i為區間的左端，j為區間的最右端。

如果已知區間的最多端i，d = k / i，可以證明j = k / d。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
int main(){
	while(~scanf("%lld%lld",&n,&k)){
		ll ans = n * k;
		if(n > k)	n = k;  //n > k，大于n的部分模值是k本身。
		for(ll i=1;i<=n;){
			ll d = k / i;    //如果i > k,d = 0。下面就不合法了
			ll j = k / d;
			if(j > n)	j = n;
			ans -= (i + j) * (j - i + 1) / 2 * d;
			i = j + 1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}