codeforces 616E Sum of Remainders (数论）

题干：

给你一个n，求n mod 1 + n mod 2 + n mod 3 + … + n mod m.即$\sum_{1}^m{nmod(i) }$∑1m​nmod(i)

思路：

$\sum_{1}^m{nmod(i) }$∑1m​nmod(i) = $\sum_{1}^m{n-(n|i)mod(i) }$∑1m​n−(n∣i)mod(i) = n*m-$\sum_{1}^m{(n|i)mod(i) }$∑1m​(n∣i)mod(i)
对于n|i(也就是n/i的整数部分)一定出现在区间[L,R]的最后一个即[n|(i+1)+1,n|i] （打表找规律得）

#include <cstdio>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cstring>
#define LL long long

using namespace std;
const LL mod = 1e9+7;
int main()
{
    LL n,m,ans=0,sum=0;
    scanf("%lld%lld",&n,&m);
    ans=((m%mod)*(n%mod))%mod;
    long long up=min(m,n);
    for(LL i=1;i<=up;i++){
    	LL r=min(n/(n/i),up);
    	LL st=r+i,num=r-i+1;
    	if(st&1)  num/=2;
    	else     st/=2;
    	sum=(sum+(st%mod)*(num%mod)%mod*((n/i)%mod))%mod;
    	i=r;
    }
    printf("%lld\n",(ans-sum+mod)%mod);
	return 0; 
}