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

Wannafly 挑战赛11

A. 水

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin>>n;
    cout<<n+1<<endl;
    return 0;
}

B: 组合数学, 预处理阶乘逆元

因为不可能暴力,所以我们想到是推式子
我们可以把前几项放在Excel表中推一下
然后我们会发现 关于m,n的式子为

常数k*b^(m-1)*a^(n-m)

该式子即为目标结果

如何求常数k呢

设k[n][m] 为n行m列的常数

我们发现 k[n][m]=k[n-1][m]+k[n-1][m-1]
这个式子和组合数学里的 C(n,k)+C(n,k+1)=C(n+1,k+1) 相似

所以 k[n][m]=C(n-1,m-1)

但因为我们无法以O(N^2)解决这道题,所以不能用递推式求组合数

那我们就直接用 组合数的公式求

C(n,m)=n!/((n-m)!*m!)

预处理n!和n!的逆元

这里因为数组有限,无法使用递推式求逆元,

所以我们用费马小定理求逆元

a^(p-1)≡1(mod p)

则 a^(p-2) 即为 a 对于 p 的逆元.

预处理即可

当n < m时,ans=0

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int maxn = 100000;

int a,b,n,m;
int T;

ll inv[maxn+10],fac[maxn+10];
///预处理N!的逆元
//费马小定理
/*
 *假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)
 *根据这个性质我们可以知道 a的逆元为a^(p-2)
 */
ll fast_pow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1ll)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1ll;
    }
    return ans;
}
void pre()
{
    inv[0]=1ll;
    fac[0]=1ll;
    for(int i=1;i<=maxn;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=fast_pow(fac[i],MOD-2ll);
    }
}
ll C(ll a,ll b)
{
    return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}

int main(){
    pre();
    scanf("%d",&T);
    for(int k=0;k<T;++k){
        scanf("%d%d%d%d",&a,&b,&n,&m);
        if(n<m){
            printf("0\n");
            continue;
        }
        int t=n-1,s=m-1;
        ll ans=1;

        ans=ans*C(n-1,m-1)%MOD*fast_pow(a,n-m)%MOD*fast_pow(b,m-1)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}


/// C(N-1,M-1)*b^(M-1)*a^(N-M)
/// N<M 0

51nod 1120 机器人走方格 V3

Type:Lucas+Catalan序列+逆元

题目

N * N的方格,从左上到右下画一条线。一个机器人从左上走到右下,只能向右或向下走。并要求只能在这条线的上面或下面走,不能穿越这条线,有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

4

Output示例

10

题解

画图会发现就是一个Catalan序列,
但我一开始没理解题意,原来只是不能跨过斜线,但可以在斜线上走…

在Excel中画了一下,因为两边是对称的,所以我们只需要求一边,将最终的答案*2即可.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=10007;

LL Pow(LL a,LL b,LL p){
    LL ans=1;
    while(b){
        if(b&1)
        {
            b--;
            ans=(ans*a)%p;
        }
        b>>=1;
        a=(a*a)%p;
    }
    return ans;
}

LL Comb(LL a,LL b,LL p)
{
    if(a < b) return 0;
    if(a == b) return 1;
    if(b > a-b) b = a-b;
    LL ans = 1, ca = 1, cb = 1;
    for(LL i=0; i<b; ++i)
    {
        ca = (ca*(a-i))%p;
        cb = (cb*(b-i))%p;
    }
    ans = (ca*Pow(cb, p-2,p))%p;
    return ans;
}
LL Lucas(LL n, LL m, LL p)
{
    LL ans = 1;
    while(n && m && ans)
    {
        ans = (ans * Comb(n%p, m%p, p))%p;
        n /= p;
        m /= p;
    }
    ///如果等于0则返回1
    return ans==0?1:ans;
}

void extgcd(LL a,LL b,LL& d,LL& x,LL& y){
    if(!b){ d=a; x=1; y=0;}
    else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
}
LL inv(LL a,LL n){
    LL d,x,y;
    extgcd(a,n,d,x,y);
    return d==1?(x+n)%n:-1;
}

int main(){
    LL N;
    while(cin>>N){
        N=N-1;
        LL d1,d2;
        LL x=Lucas(2*N,N,mod);
        LL d=inv(N+1,mod);
        //cout<<"Lucas: "<<x<<endl;
        //cout<<"Inv: "<<d<<endl;
        cout<<2*x*d%mod<<endl;
    }
    return 0;
}

51nod 1119 机器人走方格V2

Type: 组合数学,二项式定理,逆元

题目

M * N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod 10^9 + 7的结果。

Input

第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)

Output

输出走法的数量 Mod 10^9 + 7。

Input示例

2 3

Output示例

3

题解

画一下图会发现这就是杨辉三角,而我们需要求的是C(N+M-2,N-1)
用逆元和递推公式算一下就可以了

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1000000+10;
int m,n;

LL inv[maxn];
void init(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
    }
}

LL solve(int N,int M){
    ///ans=C(N,M)
    //cout<<N<<" "<<M<<endl;
    LL ans=1;
    for(int i=1;i<=M;++i){
        ans=ans*(N-i+1)*1ll%mod*inv[i]%mod;
    }
    return ans;
}

int main(){
    init();
    while(cin>>m>>n){
        cout<<solve(n+m-2,n-1)<<endl;
    }
    return 0;
}

51nod 1040 最大公约数之和

Type:欧拉函数,gcd性质,思维

题目

给出一个n,求1-n这n个数,同n的最大公约数的和。比如:n = 6
1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6,加在一起 = 15

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15

题解

N<=10^9,所以肯定无法暴力枚举
考虑我们要求 lambda(gcd(i,N) | i∈[1,N])

我们可以知道:
对于每个数N,他的约数范围在[1~N]之间,即我们可以将问题转化为(设约数为Ni,1~N中约数为Ni个数为Mi):

lambda(Ni*Mi)

假设我们已经得到了Ni,问题就在于我们如何求出Mi
设i为1~N中任意数:

(1) Mi=count(gcd(i,N)=Ni | i∈[1~N])
=count(gcd(i/Ni,N/Ni)=1 | i∈[1~N])

即我们只需要求出1~N中与N/Ni互素的数的个数即可

即 euler(N/Ni)

(2) Mi=euler(N/Ni)

ans=lambda(Ni*euler(N/Ni))

然后有一个小性质,即 i*i<=N时,我们枚举到sqrt(i)同时求出 N/i ,枚举完所有的 i 即枚举完所有 1~N 内 N 的约数.

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N;

LL euler(LL n){
    LL res=n,a=n;
    for(LL i=2;i*i<=a;++i){
        if(a%i==0){
            res=res/i*(i-1);
            while(a%i==0)a/=i;
        }
    }
    if(a>1)res=res/a*(a-1);
    return res;
}

int main(){
    while(~scanf("%lld",&N)){
        LL ans=0;
        for(LL i=1;i*i<=N;++i){
            if(N%i==0){
                ans+=(i*euler(N/i));
                if(i*i!=N){
                    ans+=((N/i)*euler(i));
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

山东省第八届ACM省赛 fireworks

迟来的祝福,新年快乐.

Link

要登录

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3895.html

Type: 杨辉三角<-组合数学,逆元

题意

假设x位置有一个烟花,则每秒烟花都会分裂到x+1与x-1这两个位置.

给你n个烟花的初始位置xi和个数ci,问你T秒后,位置w上的烟花个数有多少个.

题解

画一下样例的图会发现很像杨辉三角,我们可以将每个初始点分开计算,最后的结果就是所有初始点分裂后落在目标点的烟花个数和.
但我们发现它们的初始值大小与杨辉三角不同,并且比杨辉三角多了许多0, 然后我们考虑如何解决这两个情况.

(1) 初始值ci,因为只有一个初始点,这点和杨辉三角一样.所以答案是

ans(原杨辉三角在该位置的结果)*ci

(2) 中间有0,这点好想,我们只需要通过推导公式将实际坐标转换为逻辑坐标即可.

然后我们分情况讨论,我们在图上可以发现

(1) 当 分裂次数目标位置和原位置的距离差 同奇偶时该位置结果为0.
(2) 当距离大于T+1时(即杨辉三角第T行值的个数),永远不可能分裂到.

因为只需要考虑最后一次分裂的结果,所以只需要计算杨辉三角第T行即可,即 C(T,0~T)
预处理组合公式我们用 组合数学 性质4那个公式.
所以我们需要预处理一下1~1e5的逆元,将除法转换为乘法.
最后答案就是

ans=Sigma(i=1~n,c*C[实际位置] | 根据情况忽略i)

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 1e9+7;
const int maxn = 1e5+7;

LL C[maxn];
///逆元
LL inv[maxn];
void init_(){
    inv[1]=1;
    for(int i=2;i<maxn;++i){
        inv[i]=(MOD-MOD/i)*1ll*inv[MOD%i]%MOD;
    }
}

///快速幂模求逆元,调动方式quick_mod(i,MOD-2)
//这里我们用预处理.
LL quick_mod(LL x, int n){
    LL ret = 1;
    while(n){
        if(n & 1) ret = ret * x % MOD;
        x = x * x %MOD;
        n >>= 1;
    }
    return ret;
}

void init(int t){
    C[0]=1;
    for(int i=1;i<=t;++i){
        C[i]=C[i-1]*(t-i+1)*1ll%MOD*inv[i]%MOD;
        //printf("Num: %d %lld, INV: %lld\n",i,C[i],inv[i]);
    }
}
//判断是否同奇同偶
bool same(int x,int y){
    if((x&1)^(y&1)) return false;
    return true;
}

int query(int t,int d){
    if(t&1){
        return t/2-d/2;
    }
    return t/2+(d-1)/2;
}

int main(){
    init_();
    int n,T,w;
    while(~scanf("%d%d%d",&n,&T,&w)){
        init(T);
        LL ans=0;
        for(int i=1;i<=n;++i){
            int x,c;
            scanf("%d%d",&x,&c);
            int dist=abs(x-w);
            if(!same(T+1,dist) && dist<T+1){
                ans=(ans+c*C[query(T+1,dist)]%MOD)%MOD;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}

POJ 3090

Link

https://vjudge.net/problem/POJ-3090

Type: 欧拉函数

题意

第一象限的点(x,y),给定一个N,问你,(0,0)~(N,N)范围中有多少连接原点且连线上没有整数坐标的点?

题解

想到如果两个数互质,则他与原点的连线上,必然没有整数点.

然后原题转换成该范围内有多少个点的 x与y互质

这个与poj2478这道题求法一样,有一点不同的是,(x,y)存在的同时也会存在(y,x) 并且会同时存在(1,0)(0,1)(1,1)这三个点,所以答案是

Farey[n]*2+3

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000+100;
int phi[maxn];
int Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n,kase=1,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        printf("%d %d %d\n",kase++,n,Farey[n]*2+3);
    }
    return 0;
}

POJ 2478

Link

https://vjudge.net/problem/POJ-2478

Type: 欧拉函数

题意

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}

其中分子与分母互质.

目标是求Fn中的最简分数有多少个

题解

仔细观察会发现因为所有分数分子分母都是互素的
设n为分母,相同分母n的最简分数的个数就等于与n互质的数的个数.
分母从2开始计数

答案就是2~n的phi(k)的和

注意和斐波那契一样,Farey序列也会超过long long

Code

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000+100;
LL phi[maxn];
LL Farey[maxn];


inline void phi_table(){
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(LL i=2;i<maxn;++i){
        if(!phi[i]){
            for(LL j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}

inline void init(){
    phi_table();
    memset(Farey,0,sizeof(Farey));
    for(int i=2;i<maxn;++i){
        Farey[i]=Farey[i-1]+phi[i];
    }
}

int main(){
    init();
    int n;
    while(~scanf("%d",&n)&&n){
        printf("%lld\n",Farey[n]);
    }
    return 0;
}

POJ 2407

Link

https://vjudge.net/problem/POJ-2407

Type: 欧拉函数

题意

求小于n 且与n互质的数的个数

题解

简单欧拉,但因为是十亿的数据量,所以不能预处理

Code

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

int phi(int n){
    int ans=n;
    for(int i=2;i*i<=n;++i){
        if(n%i==0){
            ans=ans-ans/i;
            while(n%i==0){
                n/=i;
            }
        }
    }
    if(n>1){
        ans=ans-ans/n;
    }
    return ans;
}

int main(){
    int n;
    while(cin>>n&&n){
        cout<<phi(n)<<endl;
    }
    return 0;
}

UVa 11426

Link

https://vjudge.net/problem/UVA-11426

Type: 数论,欧拉函数,递推,思维

题意

输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+gcd(1,4)+…+gcd(n-1,n)

保证输出不超过long long

范围: n∈[1,4000000]

题解

首先我们应该清楚

4000000的数据,用暴力 – 对每个gcd求值相加复杂度是i*j*O(gcd) 你懂就行,这么大的复杂度肯定爆炸.

所以我们第一想法肯定是预处理.

我们设 f(n) 为 (1,n)+(2,n)+(3,n)+…+(n-1,n)
则 S(n)=f(1)+f(2)+…+f(n)

通过这个公式我们就可以递推出所有的 S(n)

S(n)=S(n-1)+f(n)

然后我们的问题就转化成了求f(n)

首先我们会自然地想到,与n互素的答案是1.即(k,n)的结果都是n的约数

我们可以按照这个约数来进行分类,

用 g(n,i)表示满足gcd(x,n)=i 且 x\<n 的正整数x的个数
则: f(n)=Sum(i*g(n,i) | i是n的约数,g(n,i)是1~n中gcd(k,n)=i的k的个数)

然后我们注意到:
-gcd(x,n)=i
-则gcd(x/i,n/i)=1
-即x/i与n/i互质

然后我们就可以将 g(n,i) 看做1~n中与 n/i 互质的数的个数,即

g(n,i) = phi(n/i)

然后我们预处理phi[maxn],预处理完以后处理f(n),这里如果用二重循环依然是接受不了的

所以我们沿用筛法的思想对f[maxn]数组进行预处理,遇到i 是 k 的约数时,直接f[k]+=(i*phi[n/i])

最后预处理S[maxn]即可

Code

/*
我们要求:
G=Sigma(i=1~N) Sigma(j=i+1~N) GCD(i,j)
N<=4000000,这样的范围二次循环+GCD肯定是不行的
所以我们考虑
f(n)=Sigma(i=1~n-1) gcd(i,n)
则
G(n)=Sigma(i=1~n) f(i)
=G(n-1)+f(n)
所以我们的问题转换为如何求f(n)

即k都是n的约数
可以按照约数进行分类,用g(n,i)表示满足 (x,n)=i且x<n的正整数x的个数
则 f(n)=sum(i\*g(n,i)|i是n的约数)

再重提: g(n,i)代表满足(x,n)=i,且x<n的正整数x的个数

我们知道,如果 (a,n)=k
则 (a/k,n/k)=1

所以我们可以理解为g(n,i)代表的是x/i与n/i互质的数的个数
即满足条件的x/i 有 phi(n/i)个
g(n,i)=phi(n/i)
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=4000000+10;
LL phi[maxn];

LL f[maxn];

LL g[maxn];
void phi_table(){
    for(int i=2;i<maxn;++i) phi[i]=0;
    phi[1]=1;
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

void init(){
    phi_table();
    memset(f,0,sizeof(f));
    for(int i=1;i<maxn;++i){
        for(int j=i*2;j<maxn;j+=i){
            f[j]+=(i*phi[j/i]);
        }
    }
    memset(g,0,sizeof(g));
    for(int i=1;i<maxn;++i) g[i]=g[i-1]+f[i];
}

int main(){
    init();
    int k;
    while(~scanf("%d",&k) && k){
        printf("%lld\n",g[k]);
    }
    return 0;
}