51Nod 1225 余数之和

Problem

F(n) = (n % 1) + (n % 2) + (n % 3) + ...... (n % n)。其中%表示Mod，也就是余数。 例如F(6) = 6 % 1 + 6 % 2 + 6 % 3 + 6 % 4 + 6 % 5 + 6 % 6 = 0 + 0 + 0 + 2 + 1 + 0 = 3。 给出n，计算F(n), 由于结果很大，输出Mod 1000000007的结果即可。

Solution

好像叫分块？不过写的不大好。。。

Code

#include<stdio.h>
#include<iostream>
typedef __int128 ll;
using namespace std;
ll n;
const ll mod=1000000007;
ll dfs(ll cur,ll cnt){
	if(cur<=4000000){
		ll ret=0;
		for(int i=1;i<=cur;i++){
			ret=(ret+n%i)%mod;
		}
		return ret;
	}
	ll nex=n/(cnt+1);
	ll chu=2,num=cur-nex;
	if(num%2==0){
		chu=1;
		num/=2;
	}
	return ((n%cur+n%(nex+1))/chu%mod*num%mod+dfs(nex,cnt+1))%mod;
}
long long s;
int main(){
	scanf("%lld",&s);
	n=s;
	long long ans=dfs(n,1)%mod;
	printf("%lld\n",ans); 
	return 0;
}