题目传送门

余数求和

题目背景

数学题，无背景

题目描述

给出正整数n和k，计算G(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如G(10, 5)=5 mod 1 + 5 mod 2 + 5 mod 3 + 5 mod 4 + 5 mod 5 …… + 5 mod 10=0+1+2+1+0+5+5+5+5+5=29

输入输出格式

输入格式：

两个整数n k

输出格式：

答案

输入输出样例

10 5

29

说明

30%: n,k <= 1000

60%: n,k <= 10^6

100% n,k <= 10^9

　　分析：

　　之前没怎么写过数论分块（蒟蒻并不会莫比乌斯反演），于是做道题练下手。

　　因为$a\%b=a-b*\lfloor \frac{a}{b}\rfloor$，所以我们所求的式子$\sum^n_{i=1}k\mod i$可以转化为$n*k-\sum^n_i{i*\lfloor\frac{k}{i}\rfloor}$。

　　和式的部分就可以用整除分块来做，复杂度就是$O(\sqrt{n})$的。

　　Code：

//It is made by HolseLee on 7th Nov 2018

//Luogu.org P2261

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

ll n,k,ans;

int main()

{

    cin>>n>>k;

    ans=n*k;

    for(ll l=,r; l<=n; l=r+) {

        if( l<=k ) r=min(k/(k/l),n);

        else r=n;

        ans-=(r-l+)*(r+l)*(k/l)/;

    }

    cout<<ans<<'\n';

    return ;

}