51 nod 1225余りの合計
タイトル:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1225
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+2+1+0=3です。
nを与え、F(n)を計算し、結果が大きいので、Mod 100000 007の結果を出力すればいいです。
Input
n*n-sigma(flor(n/i)*i)を求めています。各1<=i==nに対して、残りはn-flor(n/i)*iです。n/iの値は2*sqrt(n)個なので、特殊です。
場合は2*sqrt(n)-1個で、n/i==iの場合は、約数のように相互に対応し、かつsqrt(n)より大きいものは一回だけ出現します。必要です。
エニュメレーション1~sqrt(n)でいいです。k=n/iを取ります。対応する2つはk、n/kです。sqrt(n)より大きいのはn/k*kです。n/i==kごとに、彼らのi値はインクリメントされます。 列の中には、等差数列で和を求めることができます。ans=(a 1+an)*cou/2は、最初に現れます。 のはn/(k+1)+1で、最後に現れるのはn/kであり、またn/i==kが現れる回数、すなわちcou=n/k-n/(k+1)である。
コード:
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+2+1+0=3です。
nを与え、F(n)を計算し、結果が大きいので、Mod 100000 007の結果を出力すればいいです。
Input
1 N(2 <= N <= 10^12)。
Output F(n) Mod 1000000007 。
Inputの例6
Output例3
問題解決の考え方:n*n-sigma(flor(n/i)*i)を求めています。各1<=i==nに対して、残りはn-flor(n/i)*iです。n/iの値は2*sqrt(n)個なので、特殊です。
場合は2*sqrt(n)-1個で、n/i==iの場合は、約数のように相互に対応し、かつsqrt(n)より大きいものは一回だけ出現します。必要です。
エニュメレーション1~sqrt(n)でいいです。k=n/iを取ります。対応する2つはk、n/kです。sqrt(n)より大きいのはn/k*kです。n/i==kごとに、彼らのi値はインクリメントされます。 列の中には、等差数列で和を求めることができます。ans=(a 1+an)*cou/2は、最初に現れます。 のはn/(k+1)+1で、最後に現れるのはn/kであり、またn/i==kが現れる回数、すなわちcou=n/k-n/(k+1)である。
コード:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int mod=1000000007;
long long n;
long long ans;
long long inv(int x,int n)
{
long long temp=x,ans=1;
while(n)
{
if(n&1)
ans=(ans*temp)%mod;
temp=(temp*temp)%mod;
n=n/2;
}
return ans;
}
int main()
{
scanf("%I64d",&n);
long long cnt=inv(2,mod-2);
ans=((n%mod)*(n%mod))%mod;
//cout<<ans<<endl;
long long m=(long long)sqrt(n);
for(long long i=1;i<=m;i++)
{
if(n/i==i)
{
long long temp=n/i*i;
ans=((ans-temp)%mod+mod)%mod;
continue;
}
long long temp=(n/i+n/(i+1)+1)%mod;
long long cur=(i*(n/i-n/(i+1)))%mod;
temp=((temp*cur)%mod*cnt)%mod;
temp=(temp+(n/i)*i)%mod;
ans=((ans-temp)%mod+mod)%mod;
}
printf("%I64d
",ans);
return 0;
}