基础数论概述

。。。。。。。。。。。。。。

gcd

1
2
3
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}

ex_gcd

前面我们用欧几里得算法gcd(a,b)=gcd(b,a%b)求得a,b的最大公约数,而扩展欧几里得算法可求得ax+by=gcd(a,b)的解,进一步可得到ax+by=c的解。
原理如下:
设a>b

  • 当b=0时,显然有一对整数x=1,y=0,使得a*1+0*0=gcd(a,0);
  • 当b>0,则gcd(a,b)=gcd(b,a mod b)。假设存在一对整数x,y,满足b*x+(a mod b)*y=gcd(b,a mod b),因为bx+(a mod b)y=bx+(a-b(a/b))y=ay+b(x-(a/b)y),所以令x’=y,y’=x-(a/b)y,就得到了ax’+by’=gcd(a,b)。
  • 对于更为一般的方程ax+by=c,它有解当且仅当d|c。我们先求出ax+by=d的一组特解x0,y0,然后同时乘上c/d,就得到了ax+by=c的一组特解(c/d)x0,(c/d)y0。
    事实上,方程ax+by=c的通解可以表示为x=(c/d)x0+k(b/d),y=(c/d)y0-k(a/d) (k∈Z)。
    其中k取遍整个整数集合,d=gcd(a,b),x0,y0是ax+by=gcd(a,b)的一组特解。
    1
    2
    3
    4
    5
    6
    7
    LL exgcd(LL a,LL b,LL &x,LL &y) //扩展欧几里得算法 
    {
    if(b==0){x=1,y=0;return a;}
    LL ret=exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-y*(a/b);
    return ret; //返回值为gcd(a,b)
    }

线性筛

寻找0到n中的质数个数,i从2到sqrt(n)依次取未被标记数j,每次从j*j到n将j(当前质数)的倍数进行标记,最后剩下全为质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<math.h>
using namespace std;
int isprime(int m,int n) {
int *prime=new int[n+1];
for(int i=2; i<=n; i++)
prime[i]=1;
for(int i=2; i<=sqrt(n); i++) {
if(prime[i]==0) continue;
for(int j=i*i; j<=n; j+=i)
prime[j]=0;
}
int num=0;
for(int i=m; i<=n; i++)
num+=prime[i];
delete []prime;
return num;
}
int main() {
long long int n,m;
while(cin>>m>>n) {
cout<<isprime(m,n)<<endl;
}
return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
LL quickpow(LL x,LL n)
{
LL ans=1;
x%=Mod;
while(n>0){
if(n&1) ans=(ans*x)%Mod; //n%2==1
x=(x*x)%Mod;
n/=2;
}
return ans;
}

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
//N=∏pi^ci;
//N的所有约数和为:∏(1+pi+pi^2+...+pi^ci)
void divide(ll n){
for(ll i=2;i*i<=n;i++){
if(n%i==0){
p[++m]=i;
while(n%i==0)
n/=i,c[m]++;
}
}
if(n!=1ll) p[++m]=n,c[m]=1ll;
}

递归求等比数列和取模

Sum(p,c)=1+p+p^2+...+p^c
若p为奇数:sum(p,c)=qpow(p, (c + 1) / 2) + 1) * sum(p, c / 2);
若p为偶数:sum(p,c)=(qpow(p, c / 2) + 1) * sum(p, c / 2 - 1) + qpow(p, c);

斯特林公式

普通计算时:N!=1*2*3*4*5* ............*N
如果要计算N!后得到的数字,则我们可以知道其等于lgN!+1
lgN!=lg1+lg2+lg3+lg4+lg5+....................+lgN;
但是当N很大的时候,我们可以通过数学公式进行优化:(即Stirling公式)
N!=sqrt(2*pi*N)*(N/e)^N;(pi=3.1415926=acos(-1.0),e=2.718)lgN!=(lg(2*pi)+lgN)/2+N*(lgN-lge);
斯特林公式可以用来估算某数的大小结合lg可以估算某数的位数,或者可以估算某数的阶乘是另一个数的倍数。

威尔逊定理

当且仅当p为质数时,(p-1)!≡-1 (mod p)

判断一个组合数的奇偶性

C(n,k)为奇数时
n&k==k //n和k进行&位运算后还等于k

判断2的次方数

我们可以发现2的次方数n和n-1的二进制对应如下:
2 10 01
4 100 011
8 1000 0111
16 10000 01111
。。。。。。。。。。。。。。。
即n&(n-1)=0
而要确定n是2的几次方则直接数>>1右移次数即可

原码反码补码

  • 原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值。
  • 反码的表示方法是:正数的反码是其本身;负数的反码是在其原码的基础上, 符号位不变,其余各个位取反。
  • 补码的表示方法是:正数的补码就是其本身;负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1。 (即在反码的基础上+1)

欧拉函数

欧拉函数
φ(n)表示1~n中与n互质的数的个数

容斥原理

  • 在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复,这种计数的方法称为容斥原理
  • A∪B∪C = A+B+C - A∩B - B∩C - C∩A + A∩B∩C

欧拉定理

  • 当n,a为正整数,且a和n互质时,a^φ(n)≡1(mod n);( 即[a^φ(n)]%n≡1%n )
  • 应用:首先看一个基本的例子。令a = 3,n = 5,这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4,所以φ(5)=4。计算:a^φ(n) = 3^4 =81,而81 Ξ 1 (mod 5)。与定理结果相符。
    这个定理可以用来简化幂的模运算。比如计算7^222的个位数,实际是求7^222被10除的余数。7和10互质,且φ(10)=4。由欧拉定理知7^4Ξ1(mod 10)。所以7^222=(7^4)^55 * (7^2) Ξ 1^55 * 7^2 Ξ 49 Ξ 9 (mod 10)

费马小定理

  • a是不能被质数p整除的正整数,则有 a^(p-1) ≡ 1 (mod p)
  • 证明这个定理非常简单,由于p是质数,所以有φ(p) = p-1,代入欧拉定理即可证明。推论:对于任意正整数a,有a^p ≡ a (mod p),因为a能被p整除时结论显然成立。

费马大定理

当整数n >2时,关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。

哥德巴赫猜想

任意一个大于2的偶数,都可以写成两个质数的和

逆元

  • 当求解公式:(a/b)%m 时,因b可能会过大,会出现爆精度的情况,所以需变除法为乘法:
    设c是b的逆元,则有b*c≡1(mod m)
    (a/b)%m = (a/b)*1 %m = (a/b)*b*c %m = a*c(mod m);
    即a/b的模等于a*c的模;
  • 具体求法

高斯消元

斐波那契数列

  • 通项公式:
  • 任意两相邻斐波那契数互质
  • gcd(F(a),F(b))==F(gcd(a,b))
  • 矩阵快速幂求法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <iostream>
    #include <string.h>
    using namespace std;
    #define rep(i,a,n) for(int i=a;i<n;i++)
    #define repd(i,a,n) for(int i=n-1;i>=a;i--)
    #define CRL(a,x) memset(a,x,sizeof(a))
    const int N=1e3+5;
    const int mod=1e4;
    struct Mat{
    int data[2][2];
    Mat(){CRL(data,0);} //构造函数

    Mat operator*(const Mat &h){ //重载乘号
    Mat c;
    rep(i,0,2)
    rep(j,0,2)
    rep(k,0,2)
    c.data[i][j]=(c.data[i][j]+data[i][k]%mod*h.data[k][j]%mod)%mod;
    return c;
    }
    }Fn,c;

    void Mat_qpow(Mat &Fn,int n){//矩阵快速幂 实际上是c的n次方
    while(n){
    if(n&1) Fn=Fn*c;
    c=c*c;
    n>>=1;
    }
    }

    int main()
    {
    std::ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&~n){
    Fn.data[0][0]=Fn.data[1][1]=1;Fn.data[0][1]=Fn.data[1][0]=0;//单位阵初始化
    c.data[0][0]= c.data[0][1]=c.data[1][0]=1;c.data[1][1]=0;//常数阵初始化
    Mat_qpow(Fn,n);
    cout<<Fn.data[0][1]<<endl;
    }
    return 0;
    }
Donate comment here