洛谷 P2261 [CQOI2007]余数求和（整除分块）
传送门
首先知道这个式子是不能暴力的 ∑ i = 1 n k m o d i \sum_{i=1}^nk~mod~i ∑i=1nk mod i
根据取模的定义，我们可以化简：
∑ i = 1 n k m o d i = ∑ i = 1 n k − i ∗ ⌊ k i ⌋ = ∑ i = 1 n k − ∑ i = 1 n i ∗ ⌊ k i ⌋ \sum_{i=1}^nk~mod~i=\sum_{i=1}^nk-i*⌊\frac{k}{i}⌋=\sum_{i=1}^nk-\sum_{i=1}^ni*⌊\frac{k}{i}⌋ ∑i=1nk mod i=∑i=1nk−i∗⌊ik⌋=∑i=1nk−∑i=1ni∗⌊ik⌋
看到 ∑ i = 1 n ⌊ k i ⌋ \sum_{i=1}^n⌊\frac{k}{i}⌋ ∑i=1n⌊ik⌋很容易想到整除分块，但我们单纯的求出来的只是每一块的和，实际上每一块都是连续的，相当于是 i ∗ ( l + ( l + 1 ) + . . . + r ) i*(l+(l+1)+...+r) i∗(l+(l+1)+...+r)，然后用等差数列的公式求和即可： ( k / l ) ∗ ( r − l + 1 ) ∗ ( l + r ) / 2 (k/l)*(r-l+1)*(l+r)/2 (k/l)∗(r−l+1)∗(l+r)/2
然后就是整除分块中需要注意的边界问题，因为 n n n是有可能大于 k k k的，因此如果到后面 l > k l>k l>k时 k / l = 0 k/l=0 k/l=0，必须结束枚举，那么就是直接令 r = n r=n r=n
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+10;
ull n,k;
ull cal(){
ull ans=0;
for(ull l=1,r;l<=n;l=r+1){
if(k/l) r=min(k/(k/l),n);
else r=n; //注意
ans+=(k/l)*(r-l+1)*(l+r)/2;
}
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>k;
//for(int i=1;i<=n;i++) cout<<k/i<<endl;
cout<<n*k-cal()<<endl;
return 0;
}