给出正整数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。
输入格式
输入仅一行,包含两个整数n, k。
输出格式
输出仅一行,即j(n, k)。
数据范围
1≤n,k≤1091≤n,k≤109
输入样例:
5 3
输出样例:
7 题意:求题目所给的等式 思路:直接O(n)遍历肯定不行,我们尝试优化,首先我们 n%p = n - n/p*p 我们就可以把原式变成 n*p - 累加(1-m) n/i*i; 然后再利用除法分块原理能知道一段区间的除法值是一样的,然后用等差数列求和,然后得出值 除法分块: begin=i; end=n/(n/i); 首先n/i是被除后的值,然后我要最大的除值的最大下标位置,肯定是拿总和除以值就得出下标位置所在
#include#define maxn 200005#define mod 1000000007using 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<