@LittleRewriter 2017-10-08T03:19:26.000000Z 字数 7317 阅读 914

数学

数学

模P意义下运算

加减乘除都一样

快速幂

//求a^b%p
//递归
int ksm(int a,int b,int p){
    if(b==0) return l%p;
    int c=ksm(a,b>>1,p);
    c=c*1LL*c%p;
    if(b&1) c=c*a%p;
    return c;
}
//非递归
int ksm(int a,int b,int p){
    int ret=l%p;
    while(b){
        if(b&1) ret=ret*a%p;
        b>>=1;
        a=a*a%p;
    }
    return ret;
}

快速乘法

int ksc(int a,int b,int p){
    int ret=0;
    while(b){
        if(b&1) ret=(ret+a)%p;
        b>>=1;
        a=(a+a)%p;
    }
    return ret;
}

例题

NOIP2013 转圈游戏 P1965
n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。
现在，一共进行了 10^k轮，请问 x 号小伙伴最后走到了第几号位置。

快速幂裸题。

素数

判断

$O(\sqrt N)$ 枚举法
Miller-Rabin定理

算数基本定理

$x=\prod i_x^{p_x}$

筛法

O(nloglogn)筛

bool vis[100000];
for(int i=2;i<=n;++i){
    is(!vis[i]){
        for(int j=i;j*i<=n;++j)
            vis[j*i]=1;
    }
}

比较好写，但是有重复
欧拉筛(O(n)筛)

int mindiv[],prime[],tot;
for(int i=2;i<=n;++i){
    if(!mindiv[i]) mindiv[i]=i,prime[tot++]=i;
    for(int j=0;prime[j]*i<=n;++j){
        mindiv[prime[j]*i]=prime[j];
        if(prime[j]==mindiv[i]) break;
    }
}

保证被最小因子筛掉。
具体证明请见hzk大佬的Note吧...

gcd

gcd(a,b)=gcd(a,a-b)(更相减损术)

gcd(a,b)=gcd(b,a%b)(辗转相除法)

因此求gcd：

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

可以预处理

lcm

$lcm(a,b)=\dfrac{a}{gcd(a,b)}*b$

与分解质因数的结合：

$A=\prod p_i^{a_i}$ , $B=\prod p_i^{b_i}$
那么 $gcd(a,b)=\prod p_i^{min(a_i,b_i)}$ ， $lcm(a,b)=\prod p_i^{max(a_i,b_i)}$
由此也可以判断是否整除.

费马小定理

， 为 素 数

$a^{p-1}\equiv 1(mod \ \ p)，p为素数$
如果p不是素数请使用欧拉定理
可以用来算逆元
//以下所有运算都在取模意义下

$a^{p-1}\%p =a^{p-2}*a\%p=1$
因此逆元为

$a^{p-2}$
要求很多需要预处理
首先预处理出一个f数组，表示n!的逆元
那么有这样的关系：

$(n!)^{-1}=((n-1)!)^{-1}*n$ ,即

$f[i]=f[i-1]*i$
而对于任意一个数n，有这样的性质：

$n^{-1}=(n!)^{-1}(n-1)!$
由此可以O(n)的处理出逆元。
这个东西的证明：
https://margatroid.xyz/2017-10-04-Wilson-theorem/
一个神犇的blog
实现：

int f[],inv[];
f[0]=1;
for(int i=1;i<=n;++i) f[i]=f[i-1]*i%p;
int t=ksm(f[n],p-2,p);//快速幂，也可以exgcd
for(int i=n;i>=1;--i){
    inv[i]=t*f[i-1]%p;
    t=t*i%p;
}

exgcd

//这里没有听懂老师讲的...所以接下来的内容可能并不是笔记

裴蜀定理

若a,b 是整数, 且(a,b)=d，那么对于任意的整数x,y,ax+by 都一定是d
的倍数，特别地，一定存在整数x,y，使ax+by=d 成立。

exgcd

EXgcd用于解决这样一类问题：
已知(a,b)，求解一组(p,q)，使得pa+qb=gcd(a,b).
解是一定存在的，根据是数论中的某个相关定理。
那么怎么求呢？
pa+qb=gcd(a,b)=gcd(b,a%b)=pb+q(a%b)=pb+q(a- $\lfloor$ a/b $\rfloor$ *b)=qa+(p- $\lfloor$ a/b $\rfloor$ *q)b
$\therefore$ $p_1=q, q_2=p-\lfloor a/b \rfloor *q$
显然p、q都是单调递减的。而我们在无数次的gcd过程中，b的值最终变成0，即p*a=a，显然此时p=1,q=0是一组解。那么我们有没有办法逆推回去？答案是肯定的。
接下来的代码，就是递归的求解一组x,y

int exgcd(int a,int b,int &x,int &y){
    int t;
    if(!b) {x=1;y=0;return a;}
    t=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return t;
}

解不定方程和线性同余方程

对于方程ax+by=c，该方程有整数解的充要条件是c%gcd(a,b)=0
方程ax+by=gcd(a,b)的解为

$，其中，为任意一组整数解$
$x=x_0+bt,y=y_0-at，其中t\in Z，x_0y_0为任意一组整数解$
方程ax+by=c若有整数解，则其整数解为方程ax+by=gcd(a,b)的解乘 $\dfrac{c}{gcd(a,b)}$
当t= $\dfrac{b}{gcd(a,b)}$ 时x为最小正整数解，此时x=(x%t+t)%t

这几条定律是我们解不定方程的依据。
而方程ax $\equiv$ c(mod b) $\Leftrightarrow$ ax+by=c，直接上Exgcd就好辣

求逆元

void exgcd(int a,int b,int c,int &x,int &y){
    if(a==0){
        x=0,y=c/b;
        return;
    }else{
        int tx,ty;
        exgcd(b%a,a,tx,ty);
        x=ty-(b/a)*tx;
        y=tx;
        return;
    }
}

例题

POJ1061 青蛙的约会
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B 的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

根据小学数学，我们轻而易举的列出来这么一个方程,t为时间，p为圈数：
(x+m·t)-(y+n·t)=p·L
显然用exgcd能求出来t，p。为了方便代，我们不妨先整理一下：
(n-m)t+pL=x-y
要求条件：(x-y)%gcd(n-m,L)=0
最小正整数解：t=(t%m+m%t，其中m= $\dfrac{L}{gcd(L,n-m)}$
标程：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
const double eps(1e-9);
LL x0,y0,m,n,L;
void exgcd(LL a,LL b,LL& x,LL& y,LL& d){
    if(b){
        exgcd(b,a%b,x,y,d);
        x-=(a/b)*y;
        swap(x,y);
    }else{
        d=a;x=1;y=0;
    }
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%lld%lld%lld%lld%lld",&x0,&y0,&m,&n,&L);
    LL x,y,a,b,c;
    a=m-n;
    b=L;
    c=y0-x0;
    LL gcd;
    exgcd(a,b,x,y,gcd);
    if(c%gcd){
        puts("Impossible");
        goto ed;
    }else{
        x=c/gcd*x;
        x=(x%L+L)%L;
        printf("%lld\n",x);
    }
    ed:return 0;
}

中国剩余定理

公式法

$\begin{cases}x \equiv a_1(mod \ \ p_1)\\ x\equiv a_2(mod \ \ p_2)\\...\\ x\equiv a_n(mod \ \ p_n)\end{cases}$

令 $M=\prod p_i$ ，
那么

， 在 意 义 下

$x=(\sum^n_{i=1} a_i·\dfrac{M}{p_i}·(\dfrac{M}{p_i})^{-1，在p_i意义下})　mod M$

拉格朗日插值法

用exgcd两两合并

首先提取前两个式子，那么
$x+k_1p_1=a_1,x+k_2p_2=a_2$
相减， $k_1p_1-k_2p_2=a_1-a_2$
解出来一组 $k_1k_2$ 求出来x
可以形成一个新的式子
$X\%p_1p_2=a_{12}$
这里并不需要互素。

POJ 1006 Biorhythms
人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日期，分别对应于体力，情感，智力出现峰值的日期。然后再给出一个起始日期，要求从这一天开始，算出最少再过多少天后三个峰值同时出现。

列出三个类似(k-x)%23=0的式子。
联立即可。
标程：

#include<cstdio>
#include<algorithm>
#include<cstring>
//by zrt
//problem:
using namespace std;
const int inf=(1<<30);
typedef long long LL;
const double eps=1e-8;
int M=21252;
void exgcd(LL a,LL b,LL&d,LL&x,LL&y){
    if(!b) d=a,x=1,y=0;
    else{
        exgcd(b,a%b,d,y,x);y-=(a/b)*x;
    } 
}
LL R1,R2,R3;
int p,e,i,D;
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    LL y,d;
    exgcd(M/23,23,d,R1,y);
    exgcd(M/28,28,d,R2,y);
    exgcd(M/33,33,d,R3,y);
    R1=(M/23*R1)%M;
    R2=(M/28*R2)%M;
    R3=(M/33*R3)%M;
    int tt=0;
    while(scanf("%d%d%d%d",&p,&e,&i,&D),~p){
        printf("Case %d: the next triple peak occurs in ",++tt);
        LL ans=(R1*p+R2*e+R3*i-D)%M;
        ans=(ans+M)%M;
        if(ans==0){
            printf("%d days.\n",M);
        }else printf("%lld days.\n",ans);
    }
    return 0;
}

欧拉定理

剩余系与简系

剩余系：i的剩余系是1~i-1
简系：i的简系是剩余系中与p互素的部分

欧拉定理

$\phi(m)为m的简系元素个数。$
$如果gcd(a,m)=1,那么$

$a^{\phi(m)} \equiv 1(mod \ m)$

欧拉函数的筛法

$如果gcd(a,b)=1那么\phi(ab)=\phi(a)*\phi(b)$ 这一性质称为积性
而 $\phi(p^k)=p^k-p^{k-1}$ ，因此可以线性筛出欧拉函数

void getphi(){
    int i,j;
    phi[1]=1;
    for(i=2;i<=40000;++i){
        if(!notprime[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(j=1;j<=cnt;++j){
            if(i*prime[j]>0) break;
            notprime[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

经典数学问题

余数之和

求 $\sum^n_{i=1} X\%i$

原式= $\sum^n_{i=1} X-\lfloor \dfrac{X}{i}\rfloor *i$
不妨回想一下我们上午的那道题。 $\lfloor\dfrac{X}{i}\rfloor$ 这个东西其实可以分成 $\sqrt X$ 段，并且某一段区间这个值是相同的。
比如说，在[L,R]， $\lfloor\dfrac{X}{i}\rfloor$ =k，那么这一段区间的余数之和就是 $k*\sum_{i=L}^R i$ ，这个值可以用等差数列的公式搞一下。
而想要求这个东西也比较简单，R=X/L，这是因为这一段区间值其实是确定的。

Pick定理

$S=a+\dfrac{b}{2}-1$
一个格点多边形面积为内部格点数量+边上格点数量的一半-1
证明可以分割归纳。
QQ图片20171005184840.png

P2954
问内部的格点数量

海伦公式或者余弦定理求面积
关键是求边上的点
如果说长为a，宽为b，那么
$每\dfrac{a}{gcd(a,b)}或\dfrac{b}{gcd(a,b)}均会遇到一个整点$
这是因为每次的增长其实是在一条直线上，而gcd(a,b)其实是第一个交点的出现的位置。因此我们其实是求最小化的东西。
因此每边上有 $\dfrac{a}{gcd(a,b)}+1$ 个整点。

矩阵乘法与矩阵快速幂

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            c[i][j]+=a[i][k]*b[k][j];

由此可以快速求一个递推式 $f(n)=a_1f(n-1)+a_2f(n-2)+...+a_kf(n-k)$

$\left(f_n,f_{n-1},...,f_{n-k+1},f_{n-k}\right) \cdot \left( \begin{matrix} a_1&1&0&...&0&0 \\a_2&0 &1&...&0&0\\...&...&...&...&...&...\\a_{k-1}&0&0&...&0&1\\a_k&0&0&...&0&0\end{matrix} \right)=(f_{n+1},f_n,...,f_{n-k+2},f_{n-k+1})$

矩阵快速幂=矩阵乘法+快速幂

例斐波那契数列快速求值

对斐波那契数列，

$\left( f_{n},f_{n-1}\right) \cdot \left( \begin{matrix} 1& 1\\ 1& 0\end{matrix} \right)=(f_{n+1},f_n)$
ksm即可
标程：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
//by zrt
//problem:
using namespace std;
typedef long long LL;
const int inf(0x3f3f3f3f);
const double eps(1e-9);
LL x0,y0,m,n,L;
void exgcd(LL a,LL b,LL& x,LL& y,LL& d){
    if(b){
        exgcd(b,a%b,x,y,d);
        x-=(a/b)*y;
        swap(x,y);
    }else{
        d=a;x=1;y=0;
    }
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    scanf("%lld%lld%lld%lld%lld",&x0,&y0,&m,&n,&L);
    LL x,y,a,b,c;
    a=m-n;
    b=L;
    c=y0-x0;
    LL gcd;
    exgcd(a,b,x,y,gcd);
    if(c%gcd){
        puts("Impossible");
        goto ed;
    }else{
        x=c/gcd*x;
        x=(x%L+L)%L;
        printf("%lld\n",x);
    }
    ed:return 0;
}

分治乘法

$O(n^{log_2^3})$
例如， $123456*654321=(123*10^3+456)*(654*10^3+321)$
对于 $ac + adx + bcx + bdx^2$ ，(a + b)(c + d) = ac + ad + bc + bd
然后求出ad+bc可以求得结果
这样分治一下可以快一点

组合数

《组合数学》

$C_m^n=\dfrac{n!}{m!·(n-m)!}$
求法：
C[n][m]=C[n-1][m]+C[n-1][m-1]
Lucas定理 C[n][m]%p=C[n%p][m%p]*C[n/p][m/p]
因此C[abcde][fghij]=C[a][f]*C[b][g]*C[c][h]*C[d][i]*C[e][j]

数学

模P意义下运算

快速幂

快速乘法

例题

素数

判断

算数基本定理

筛法

gcd

gcd(a,b)=gcd(a,a-b)(更相减损术)

gcd(a,b)=gcd(b,a%b)(辗转相除法)

lcm

与分解质因数的结合：

费马小定理

exgcd

裴蜀定理

exgcd

解不定方程和线性同余方程

求逆元

例题

中国剩余定理

公式法

用exgcd两两合并

欧拉定理

剩余系与简系

欧拉定理

欧拉函数的筛法

经典数学问题

余数之和

Pick定理

矩阵乘法与矩阵快速幂

分治乘法

组合数

内容目录

选择主题