51nod 1225 余数之和

Type:逆元,数论,思维,同余定理

直接上代码,题解在代码中,这道题有点耗时间,但挺有趣的

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
LL N;
/*打表
void Table(int NN){
    for(int i=1;i<=NN;++i){
        printf("%04d-%04d ",i,NN%i);
    }
}
*/
LL fast_mod(LL a,LL n,LL Mod){
    LL ans=1;
    while(n){
        if(n&1){
            ans=(ans*a)%Mod;
        }
        a=(a*a)%Mod;
        n>>=1;
    }
    return ans;
}

LL inv2=fast_mod(2,mod-2,mod);
///对照算法
LL hh(){
    LL n=N;
    LL ans;
    ans=n%mod*(n%mod)%mod;
    for(LL t,r,i=1;i<=n;++i) {
        t=n/i;
        r=n/t;
        ans=ans-((r-i+1)%mod*((r+i)%mod))%mod*inv2%mod*t%mod;
        while(ans<0) ans+=mod;
        i=r;
    }
    return ans;
}

///本来想的是计算当前N/i相同的数量--结果为:
///(N-tmp*i)/i 即计算在 N-当前数字*(N/i)后还有多少个数字可以
///整分给(N/i),由于这个方法利用了除法,所以处理除法溢出有点麻烦
///1e9左右就炸掉了
///乘法溢出也很麻烦

///最好的方法就是 N/tmp 理解为最后一个除以 N 等于 tmp 的数字是几

///式子: F[N]=N*N-Sigma(N/i*i | i∈[1,N])
///其中 括号内的式子的 N/i 有sqrt(n)个不同的值
///证: 设 tmp=100/i 则 tmp*i=100 故 Count(tmp)<=sqrt(100)
///并且可以看出 相同的 N/i 对应的 i 是连续的.
///即我们可以用等差数列求和公式来求 当 tmp=N/i 时 i 的和
///用等差数列求和时/2用 2的逆元来做\

///自己坐着坐着就莫名其妙和他一样了= =
LL solve(){
    LL ans=N%mod*(N%mod)%mod;
    for(LL i=1;i<=N;){
        LL tmp=N/i;
        LL t=N/tmp;
        tmp=((i+t)%mod*((t-i+1)%mod))%mod*inv2%mod*tmp%mod;
        ans=(ans%mod-tmp%mod+mod)%mod;
        i=t+1;
    }
    return ans;
}

void dui_pai(){
    for(LL i=1;i<=1000000;++i){
        N=i;
        if(hh()!=solve()) printf("%lld Faild\n",N);
    }
    puts("Done");
}

int main(){
    //dui_pai();
    while(~scanf("%lld",&N)){
        printf("%lld\n",solve());
    }
    return 0;
}