UVA1363

· · 题解

实际上思路很简单，推荐做这道题之前，自己了解一下整数分块

推荐学习.整数分块

分析

这道题是让我们求

\sum\limits_{i=1}^n k\bmod i

实际上，还可以把这个式子写成

\sum\limits_{i=1}^nk-\left\lfloor\dfrac{k}{i}\right\rfloor \cdot i

也就等于

n\cdot k - \sum\limits_{i=1}^n\left\lfloor\dfrac{k}{i}\right\rfloor \cdot i

通过整数分块，也就能知道

\sum\limits_{i=l}^r\left\lfloor\dfrac{k}{i}\right\rfloor

这个式子的权值始终唯一

所以设 T=\left\lfloor\dfrac{k}{i}\right\rfloor

由设可得

\sum\limits_{i=l}^rT \cdot i=\sum\limits_{i=l}^rT \cdot \sum\limits_{i=l}^ri

代码实现自然就简单了

只不过要记住坑点，有多组测试数据！

#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long ans;
int main(){
    while(cin>>n>>k){
        ans=n*k;
        for(long long l=1,r;l<=n;l=r+1){
            r=(k/l==0)?n:min(n,k/(k/l));
            ans-=(((l + r)*(r-l+1))>>1)*(k/l);
        }
        printf("%lld\n",ans);
    }
    return 0;
}