欧几里得算法

就是求最大公约数的辗转相除法。

数学公式

gcd⁡(a,b)={gcd⁡(b,a mod b),b≠0a,b=0\gcd(a, b)= \begin{cases} \gcd(b,a\bmod b) &,b\neq 0\\ a &,b=0 \end{cases}

模板

1
2
3
4
5

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

拓展欧几里得(exgcd)

适用问题

给定正整数 a,ba,b，求出 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 的一组正整数解。

算法思路

由欧几里得算法得出 ax+by=gcd⁡(a,b)=gcd⁡(b,a mod b)ax+by=\gcd(a,b)=\gcd(b,a\bmod b)，代回原式，即为：

bx′+a mod b×y′=gcd⁡(b,a mod b)bx^{\prime}+a\bmod b\times y^{\prime}=\gcd(b,a\bmod b)

假设我们已知上式的一组解 x′,y′x^{\prime},y^{\prime}，可以得到：

ax+by=gcd⁡(a,b)=bx′+a mod b×y′=bx′+(a−⌊ab⌋×b)y′=ay′+b(x′−⌊ab⌋×y′)\begin{aligned} ax+by=\gcd(a, b) &=b x^{\prime}+a \bmod b\times y^{\prime} \\ &=b x^{\prime}+(a-\lfloor \frac{a}{b} \rfloor \times b) y^{\prime}\\ &=a y^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime}) \end{aligned}

所以

ax+by=ay′+b(x′−⌊ab⌋×y′)x=y′y=x′−ab×y′\begin{aligned} ax+by&=ay^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime})\\ x&=y^{\prime}\\ y&=x^{\prime}-\frac{a}{b}\times y^{\prime} \end{aligned}

我们发现，当 b=0b=0 时，a×1+b×0=aa\times 1+b\times 0=a，有一组解

{x=1y=0\begin{cases} x=1\\ y=0 \end{cases}

模板

直接递归求解即可

1
2
3
4
5
6
7
8
9
10
11
12

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

这时，我们已经得到了一组解，下一步是求解 ax+by=cax+by=c。

求解 ax+by=cax+by=c

接下来我们需要分类讨论。

设 g=gcd⁡(a,b)g=\gcd(a,b)。

当 c mod b≠0c\bmod b\neq0 时，无解。

否则，令 k=cgk=\frac{c}{g}，

则

ax′k+by′k=g×k=cax^{\prime}k+by^{\prime}k=g\times k=c

得

{x=x′ky=y′k\begin{cases} x=x^{\prime}k\\ y=y^{\prime}k \end{cases}

设 xx 的周期 T=bgT=\frac{b}{g}，则最小正整数解为 (x mod T+T) mod T(x\bmod T+T)\bmod T。

乘法逆元

定义

已知 a,pa,p，求 ax≡1(modp)ax\equiv 1\pmod{p} 中的 xx，称 xx 为 aa 关于 pp 的逆元。

求解

直接求解 ax+py=1ax+py=1 即可。

最终答案为 (x mod p+p) mod p(x\bmod p+p)\bmod p。

费马小定理

当 pp 为素数时，aa 关于 pp 的逆元是 ap−2a^{p-2}。

数论分块

balabala

a mod b=a−b×⌊ab⌋a\bmod b=a-b\times\lfloor\frac{a}{b}\rfloor

一些题

P1516 青蛙的约会

Problem Link

这是一道比较裸的拓欧题。

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

#define int ll
int x,y,m,n,l;
int p,q;
int exgcd(int a,int b,int &x,int &y) {
    if(b==0) {
        x=1;
        y=0;
        return a;
    }
    int g=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return g;
}
signed main() {
    x=read();y=read();m=read();n=read();l=read();
    int a=n-m,b=x-y;
    if(a<0) {
        a=-a;
        b=-b;
    }
    int ans=exgcd(a,l);
    if(b%ans!=0) {
        cout<<"Impossible"<<endl;
    }
    else {
        cout<<((p*(b/ans))%(l/ans)+l/ans)%(l/ans)<<endl;
    }
    return 0;
}

CF1114C Trailing Loves

首先从 1010 进制开始分析。求 pp 末尾 00 的数量即为求 pp 的因数中含有 22 和 55 的数量的最小值。

例如设 x1=23×52x_1=2^3\times 5^2，则 x1x_1 的末尾 00 的数量即为 min⁡(3,2)=2\min(3,2)=2。

接下来考虑 (n!)b(n!)_b 的末尾 00 的数量。我们先枚举 bb 的因数 b=p1a1×p2a2×…×pkakb=p_1^{a_1}\times p_2^{a_2}\times \ldots \times p_k^{a_k}，若 pimp_i^{m} 是 n!n! 的一个因数，则其对答案的贡献为 ⌊mai⌋\lfloor \dfrac{m}{a_i}\rfloor。

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

const int N=2e6+10;
int n,b;
int pri[N],cnt=0;
int t[N];
int ans=INF;
signed main() {
    n=read();b=read();
    for(int i=2;i*i<=b;i++) {
        if(b%i==0) {
            pri[++cnt]=i;
            while(b%i==0) b/=i,t[cnt]++;
        }
    }
    if(b>1) pri[++cnt]=b,t[cnt]++;
    for(int i=1;i<=cnt;i++) {
        int nt=n;
        int sum=0;
        while(nt) {
            sum+=nt/pri[i];
            nt/=pri[i];
        }
        ans=min(sum/t[i],ans);
    }
    printf("%lld\n",ans);
    return 0;
}

CF1493D GCD of an Array

由于一个集合的最大公因数的一个质因数的指数是这个集合中该质数指数的最小值，可以想到每次动态维护集合 gcd 时，考虑将 yy 分解质因数 y=p1e1×p2e2×…×pkeky=p_1^{e_1}\times p_2^{e_2}\times \ldots \times p_k^{e_k}，如果集合中除 axa_x 以外的其他元素均有可以对答案产生贡献的因数 pip_i，那么答案就可以加入 pip_i 产生的贡献。

形式化的，如果我们定义 vp(ai)v_p(a_i) 为 aia_i 中质因数 pp 的指数，那么若满足

min⁡(vp(a1),…,vp(ax−1),vp(y),vp(ax+1),…,vp(an))>min⁡(vp(a1),vp(a2),…,vp(an))\min(v_p(a_1), \ldots, v_p(a_{x-1}), v_p(y), v_p(a_{x+1}), \ldots, v_p(a_n)) > \min(v_p(a_1), v_p(a_2), \ldots, v_p(a_n))

设 AA 为上述两式的差值，则对答案的贡献为 pAp^A。

接下来考虑如何求。可以用线性筛预处理质数，每次操作用预处理的最小质因子分解。

我们用 multiset 记录质数 pp 出现在的元素下标，tt 数组记录 pp 在多少个不同的元素中出现。当执行一次操作时，判断是否能够给答案产生贡献。如果能，那么插入当前的下标，随后暴力将 multiset 中的 1∼n1\sim n 下标删除一次。

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
43
44
45
46
47
48
49
50

const int N=2e5+10;
int n,m;
int a[N];
multiset<int> st[N];
int b[N];
int prime[N];
int cnt=0;
int t[N];
int ans=1;
void pri(int n) {
    for(int i=2;i<=n;i++) {   
        if(!b[i]) b[i]=i,prime[++cnt]=i;
        for(int j=1;j<=cnt;j++) {
            if(prime[j]>b[i] || prime[j]>n/i) break;
            b[i*prime[j]]=prime[j];
        }
    }
}
void modify(int p,int x) {
    while(x!=1) {
        int minn=b[x];
        if(st[minn].find(p)==st[minn].end()) t[minn]++;
        st[minn].insert(p);
        if(t[minn]==n) {
            for(int i=1;i<=n;i++) {
                st[minn].erase(st[minn].find(i));
                if(st[minn].find(i)==st[minn].end()) t[minn]--;
            }
            ans=(ans*minn)%mod;
        }
        x/=minn;
    }
}
signed main()
{
    pri(N-1);
    n=read();m=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();
    }
    for(int i=1;i<=n;i++) {
        modify(i,a[i]);
    }
    while(m--) {
        int p=read(),x=read();
        modify(p,x);
        printf("%lld\n",ans);
    }
    return 0;
}