51nod 1225:余数之和

传送门

题意

略

分析

\(\sum_i^n(n\%i)=\sum_i^n(n-i*n/i)=n^2-\sum_i^ni*n/i\)

\(=\sum r\sum_i^ni[n/i==r]\)

可以证明r不会超过\(\sqrt n\)个，复杂度O(\(\sqrt n\))

注意乘法爆long long的处理

代码

#include <bits/stdc++.h>

using namespace std;

//efine ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#define INF 0x3f3f3f3f3f3f3f3f

#define ll long long

const ll mod = 1e9+7;

const ll M = 5e8+4;

ll n,ans;

int main()

{

    scanf("%lld",&n);

    ans=n%mod*(n%mod)%mod;

    for(ll i=1,j;i<=n;i=j+1)

    {

        j=n/(n/i);

        ans = ans-(i + j)%mod * ((j - i + 1)%mod)%mod * M % mod * (n/i) % mod;

        while(ans<0) ans+=mod;

    }

    printf("%I64d\n",ans);

    return 0;

}

巴特西

51nod 1225:余数之和

传送门

题意

分析

代码

最新文章

热门文章