最新更新

1.gcd&exgcd

1.gcd: 辗转相除。

int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}

2.exgcd:
裴蜀定理：对于任意正整数a，b，一定存在非零数对（x,y),满足ax+by=gcd(a,b).
$gcd(a,b)=gcd(b,a\%b)$
设$x’,y’$是方程$ by’+ (a \% b) x’ =gcd(b,a\%b) $的解
$ by’+ (a \% b) x’ =gcd(a,b) $
$ by’+ (a-b(a/b)) x’ =gcd(a,b) $
$ ax’+by’-b(a/b)x’ =gcd(a,b) $
$ ax’+b(y’-(a/b)x’) =gcd(a,b) $
$x=x’,y=y’-(a/b)x’$

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

附一个极清晰的解释

2.欧拉函数和欧拉定理

$\phi(n)$ 表示小于等于 $n$ 且与 $n$ 互质的数的个数。
$\phi(n)=n\prod_{p|n} (1-\frac 1 p)$
特别地，$\phi(1)=1$.
感性理解一下。证明不会

在n以内所有与n互素的所有数之和为n*Φ(n)/2。

1.$O(\sqrt n)$ 筛质因数求欧拉函数。
@墨染空 的代码

int phi = x;
for(int j = 2; j * j <= x; j++){
    if(x % j == 0){
            phi = phi / j * (j - 1);
            while(x % j == 0) x /= j; 
        }
}
if(x > 1) phi = phi / x * (x - 1);

2.$O(n)$ 线性筛出$1-n$的$\phi (i)$
由定义可知，$\phi (p) =p-1$
如果$p|x,\phi (px)=p \phi(x)$
否则,$\phi (px)=(p-1) \phi(x)$
证明不会
这份是我的代码

phi[1]=1;
for(int i=2;i<=n;i++){
    if(!vis[i]) p[++cnt]=i,phi[i]=i-1;
    for(int j=1;j<=cnt&&i*p[j]<=n;j++){
        vis[i*p[j]]=1;
        if(i%p[j]==0){
            phi[i*p[j]]=phi[i]*p[j];
            break;
        }
        phi[i*p[j]]=phi[i]*(p[j]-1);
    }
}

欧拉定理：当 $gcd(a, n) = 1$，$a^{\phi (n)} \equiv 1 \bmod n$

3.逆元

两种。

1.费马小定理(p为质数)
$a^{p-1} \equiv 1 \bmod p$
$a^{p-2} \equiv \frac 1 p \bmod p$
$inv(x)=x^{p-2} \bmod p$
快速幂。

2.exgcd
$xinv(x) \equiv 1 \bmod p$
设$s=inv(x)$
$xs \equiv 1 \bmod p$
$xs+pt=1$
exgcd。

还有线性的。

iv[0] = iv[1] = 1;
for(int i = 2; i <= n; i++) 
    iv[i] = 1ll * iv[p % i] * (p - p / i) % p;

4. 欧拉筛

线性筛素数。在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
const int N = 1e8 + 10;
int n, q, p[N], cnt;
bool vis[N];
void init() {
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && p[j] * i <= n; j++) {
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
    return;
}
int main(){
    scanf("%d%d", &n, &q);
    init();
    for(int i = 1, k; i <= q; i++) 
        scanf("%d", &k), printf("%d\n", p[k]);
    return 0;
}

5.crt&excrt

crt不会 反正excrt挺好的。
模板题
现在有n个形如$ x \equiv a_i \pmod {b_i}$的方程
假设前k-1个方程的最小正整数解是$ans_{k-1},$
令$M=gcd(b_1,b_2,……,b_{k-1})$
设$ans_k=ans_{k-1}+xM(x为整数)$
则$ans_{k-1}+xM \equiv a_k \pmod {b_k}$
$∴Mx\equiv {{a_k}-{ans_{k-1}}} \pmod {b_k}$
$Mx+{b_k}y={{a_k}-{ans_{k-1}}} $
exgcd。
题目的a,b读入是反的，注意。 还有记得开longlong。

/*
exCRT 正常做法。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
const int N = 1e5 + 10;
int n; ll ai[N], bi[N];
void exgcd(ll a, ll b, ll &x, ll &y, ll &d) {
    if(b == 0) x = 1, y = 0, d = a;
    else exgcd(b, a % b, y, x, d), y = y - a / b * x;
    return;
}
ll gcd(ll x, ll y) {
    return (y == 0) ? x : gcd(y, x % y);    
}
ll mul(ll x, ll y, ll mod) {
    ll ret = 0;
    while(y) {
        if(y & 1) ret = (ret + x) % mod;
        x = (x + x) % mod; y >>= 1;
    }
    return ret;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%lld%lld", &ai[i], &bi[i]);
    ll M = 1, ans = 0;
    for(int i = 1; i <= n; i++) {
        ll z = (bi[i] % ai[i] + ai[i] - ans % ai[i]) % ai[i];
        ll x, y, d; exgcd(M, ai[i], x, y, d);
        if(z % d) return puts("-1"), 0;
        x = mul(x, z / d, ai[i] / d);
        ans = ans + M * x;
        M = M * (ai[i] / d);
        ans = (ans % M + M) % M;
    }
    printf("%lld\n", ans);
    return 0;
}

正常版本的CRT的题解

/*
CRT 正常做法。 
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
const int N = 15;
int n, a[N], b[N];
void exgcd(ll a, ll b, ll &x, ll &y, ll &d) {
    if(b == 0) x = 1, y = 0, d = a;
    else exgcd(b, a % b, y, x, d), y = y - a / b * x;
    return;
}
ll gcd(ll x, ll y) {
    return (y == 0) ? x : gcd(y, x % y);    
}
int main(){
    scanf("%d", &n);
    ll M = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        M = M * a[i] / gcd(a[i], M);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        ll x, y, d, m = M / a[i]; exgcd(m, a[i], x, y, d);
        x = (x % a[i] + a[i]) % a[i];
        ans = (ans + 1ll * b[i] * m % M * x % M) % M;
    }
    printf("%lld\n", ans);
    return 0;
}

以下为乱搞做法

/*
CRT
自己随便推一推推出来的，估计会爆ll。所以只能快速乘。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
const int N = 15;
int n, a[N], b[N]; ll nA;
void exgcd(ll a, ll b, ll &x, ll &y, ll &d) {
    if(b == 0) x = 1, y = 0, d = a;
    else exgcd(b, a % b, y, x, d), y = (y - (a / b * x) % nA) % nA;
    return;
}
ll mul(ll x, ll y) {
    ll ret = 0;
    while(y) {
        if(y & 1) ret = (ret + x) % nA;
        x = (x + x) % nA; y >>= 1;
    }
    return ret;
}
int main(){
    scanf("%d", &n);
    scanf("%d%d", &a[1], &b[1]);
    ll A = a[1], B = b[1];
    for(int i = 2; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        ll x, y, d; 
        nA = A * a[i] / __gcd(A, (ll)a[i]);
        exgcd(A, a[i], x, y, d);
        x = (x % nA + nA) % nA;
        x = mul(x, ((b[i] - B) % nA + nA) % nA);
        ll X = (mul(A, x) + B) % nA;
        A = nA; B = X;
        assert(B % a[i] == b[i]);
    }
    printf("%lld\n", (B % A + A) % A);
    return 0;
}

/*exCRT 乱搞*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define pb push_back
#define PII pair<int, int>
#define PLL pair<ll, ll>
const int N = 1e5 + 10;
int n;ll a[N], b[N]; ll nA;
void exgcd(ll a, ll b, ll &x, ll &y, ll &d) {
    if(b == 0) x = 1, y = 0, d = a;
    else exgcd(b, a % b, y, x, d), y -= a / b * x;
    return;
}
ll mul(ll x, ll y) {
    ll ret = 0;
    while(y) {
        if(y & 1) ret = (ret + x) % nA;
        x = (x + x) % nA; y >>= 1;
    }
    return ret;
}
ll gcd(ll x, ll y) {
    return (y == 0) ? x : gcd(y, x % y);
}
int main(){
    scanf("%d", &n);
    scanf("%lld%lld", &a[1], &b[1]);
    ll A = a[1], B = b[1];
    for(int i = 2; i <= n; i++) {
        scanf("%lld%lld", &a[i], &b[i]);
        ll x, y, z = b[i] - B, d;
        exgcd(A, a[i], x, y, d); 
        if(z % d) return puts("-1"), 0;
        nA = A * (a[i] / d);
        z = (z % nA + nA) % nA;
        x = (mul(x, z / d) % nA + nA) % nA;
        ll X = (mul(A, x) + B) % nA;
        A = nA; B = X;
    }
    printf("%lld\n", (B % A + A) % A);
    return 0;
}
/*
3
9982 923
9983 1234
9985 4321
*/