数论quq

一 . 最大公约数

gcd（a,b）= gcd（b,a mod b）

二 . 最小公倍数

lcm（m,n）=（m*n）/ gcd（m,n）

三 . 逆元

1.定义：在mod p的意义下，x 的乘法逆元 x^(-1)满足x*x^(-1) ≡ 1 （mod 7）即 x*x^(-1)%p=1

              x 的乘法逆元 x^(-1)存在且唯一，用inv[ x ]表示

              符合结合律时，可在过程中任意取模，包括最值，求和，加法，减法，乘法  例如a*b（mod p）==（a%p）*（b%p）

              但除法时不适用

2.应用：求a / b（mod p）时，a 过大时，由于a / b=a*inv[ b ]（mod p），可以通过求inv[ b ]计算，此时就可以过程中取模

3.求乘法逆元：

          扩展欧几里得：a*inv[a]≡1 (mod b)等同于(a*inv[a])%b==1等同于inv[a]*a+yb==1等同于gcd（a,b)==1,所以a与b互质，求inv[a]*a+yb==1中inv[a]用扩展gcd

#include<iostream>
using namespace std;
long long x,y;
void exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
}
int main()
{
    long long a,b;
    cin>>a>>b;
    exgcd(a,b,x,y);                
    cout<<(x%b+b)%b<<endl;        //x可能是负数，而x%b<b，所以要加上一个b
}

               费马小定理：若p为素数，a为正整数，则有a ^（p-1）≡ 1(mod p),所以inv[ a ] = a^（p-2）

#include<cstdio>
#define ll long long
using namespace std;
ll n,p;
ll kuai(ll x,ll k)
{
    ll ans=1;
    while(k)
    {
        if(k&1) ans=(ans*x)%p;
        x=(x*x)%p;
        k>>=1;
    } 
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&p);
    for(int o=1;o<=n;o++)  printf("%lld
",kuai(o,p-2));
}

                   线性算法: 时间复杂度O(n)

inv[1] = 1;
for(int 2 = 1; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;