其实和昨天写的那道水题是一样的,注意爆LL
$1<=n,k<=1e9$,$\sum\limits_{i=1}^{n}(k \mod i) = nk - \sum\limits_{i=1}^{min(n,k)}\lfloor\frac{k}{i}\rfloor i$
/** @Date : 2017-09-21 19:55:31* @FileName: HDU 2620 分块底数优化 暴力.cpp* @Platform: Windows* @Author : Lweleth (SoungEarlf@gmail.com)* @Link : https://github.com/* @Version : $Id$*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8;int main()
{LL n, k;while(cin >> n >> k){LL ans = n * k;int ma = min(n, k);for(LL i = 1, j; i <= ma; i = j + 1){j = (k / (k / i));if(j > ma)j = ma;LL t = 0;if((i + j) % 2)//注意溢出的问题t = (j - i + 1) / 2LL * (i + j);else t = (i + j) / 2LL * (j - i + 1);ans -= t * (k / i);}printf("%lld\n", ans);}return 0;
}