給出正整數(shù)n和k，計算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。

輸入格式

輸入僅一行，包含兩個整數(shù)n, k。

輸出格式

輸出僅一行，即j(n, k)。

數(shù)據(jù)范圍

1≤n,k≤1091≤n,k≤109

輸入樣例：

5 3

輸出樣例：

7



題意：求題目所給的等式
思路：直接O（n）遍歷肯定不行，我們嘗試優(yōu)化，首先我們 n%p = n - n/p*p 我們就可以把原式變成 n*p - 累加（1-m） n/i*i;
然后再利用除法分塊原理能知道一段區(qū)間的除法值是一樣的，然后用等差數(shù)列求和，然后得出值

除法分塊：
begin=i;
end=n/(n/i);
首先n/i是被除后的值，然后我要最大的除值的最大下標位置，肯定是拿總和除以值就得出下標位置所在

#include<bits/stdc++.h> #define maxn 200005 #define mod 1000000007 using namespace std; typedef long long ll; ll n,m; int main(){cin>>m>>n;ll x=n*m;ll sum=0;if(m>=n){m=n;} for(int i=1;i<=m;i=n/(n/i)+1){ll q=n/(n/i); q=min(q,m);ll z=(i+q)*(q-i+1)/2;sum+=z*(n/i);}cout<<x-sum; }

?

轉載于:https://www.cnblogs.com/Lis-/p/11000920.html

總結

以上是生活随笔為你收集整理的AcWing 199. 余数之和 （除法分块）打卡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。