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;
}

HDU 1021

Link

https://vjudge.net/problem/HDU-1021

Type: 数论,同余定理和余数性质,找规律也可以

题意

f(n)=f(n-1)+f(n-2) f(0)=7,f(1)=11

问:

给你一个数n,如果f(n)整除3,则输出yes,否则no.

题解

(1) 暴力输出一波会发现如果 n%4==2,则输出yes

(2) 正解:

问题可以转换成 f(n)%3 是否等于0
那么我们只需要记录下每个 f(n)%3 的值即可
f(n)≡(f(n-1)+f(n-2))(mod 3) n>=2
f(n)=((f(n-1)%3)+(f(n-2)%3))%3

Code

1-找规律

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n%4==2){
            printf("yes\n");
        }else{
            printf("no\n");
        }
    }
    return 0;
}

2-正解

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int m[maxn];

void init(){
    m[0]=7,m[1]=11;
    for(int i=2;i<=1000000;++i){
        m[i]=((m[i-1]%3)+(m[i-2]%3))%3;
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)){
        printf("%s\n",(!m[n])?"yes":"no");
    }
    return 0;
}