除法分块

除法分块 是指使用分块计算的方法求S=∑i=1n⌊ki⌋S=\sum^{n}_{i=1}{\lfloor{\frac{k}{i}}\rfloor}S=i=1∑n⌊ik⌋的值。

举个例子。当 n=20n=20n=20 时，有

iii	111	222	333	444	555	666	777	888	999	101010	111111	121212	………
⌊20i⌋\lfloor\frac{20}{i}\rfloor⌊i20⌋	202020	101010	666	555	444	333	222	222	222	222	111	111	………

我们可以把 ∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n] 分成若干块，使得每块的 ∀i\forall i∀i 除 nnn 的值向下取整后相等。

∴S=20+10+6+5+4+3+2×4+1×10\therefore S=20+10+6+5+4+3+2\times4+1\times10∴S=20+10+6+5+4+3+2×4+1×10。

题目描述 luogu2261\text{luogu2261}luogu2261

给出正整数 nnn 和 kkk 计算 G(n,k)=k &VeryThinSpace;mod&VeryThinSpace; 1+k &VeryThinSpace;mod&VeryThinSpace; 2+k &VeryThinSpace;mod&VeryThinSpace; 3+⋯+k &VeryThinSpace;mod&VeryThinSpace; nG(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ nG(n,k)=k mod 1+k mod 2+k mod 3+⋯+k mod n的值。

输入格式

两个整数 n,kn,kn,k。

输出格式

答案。

输入样例

10 5

输出样例

说明

对于 30%30\%30% 的数据，有 n,k≤1000n , k \leq 1000n,k≤1000；

对于 60%60\%60% 的数据，有 n,k≤106n , k \leq 10^6n,k≤106；

对于 100%100\%100% 的数据，有 n,k≤109n , k \leq 10^9n,k≤109。

Solution 2261\text{Solution 2261}Solution 2261

根据定义，有 kmod  n=k−n×⌊kn⌋k\mod n=k-n\times\lfloor\frac{k}{n}\rfloorkmodn=k−n×⌊nk⌋

依题意得G(n,k)=∑i=1n(kmod  i)=∑i=1n(k−i×⌊ki⌋)=nk−∑i=1n(i×⌊ki⌋)\begin{aligned}
G(n,k)&=\sum_{i=1}^{n}{(k\mod i)}\\
&=\sum_{i=1}^{n}{(k-i\times\lfloor\frac{k}{i}\rfloor)}\\
&=nk-\sum_{i=1}^{n}{(i\times\lfloor\frac{k}{i}\rfloor)}
\end{aligned}G(n,k)=i=1∑n(kmodi)=i=1∑n(k−i×⌊ik⌋)=nk−i=1∑n(i×⌊ik⌋)

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll n,k;

int main(){

   scanf("%lld%lld",&n,&k);

   ll ans=n*k,r;

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

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

   	else r=n;

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

   }

   printf("%lld",ans);

}

巴特西

除法分块 luogu2261 (坑)