CMSS 20200723

数论

gcd

$(a,a)=(0,a)=a$

$if ~a|b~ ~(a,b)=a$

$(a,b)=(a,a+b)=(a,ka+b)$

$(ka,kb)=k(a,b)$

$(a,b,c)=((a,b),c)$

若$(a,b)=1$那么$a$与$b$互质

推论$gcd(a,b)=gcd(b,a\%b)$在斐波那契数列相邻两项复杂度最大为$log_{2}(a)$

例题

CF664A

给你若干个整数,它们是$a,a+1,a+2,…,b$请求出它们的最大公约数,即 $gcd(a, a+1, a+2, …, b)$。

仅需判断是否为$a=b$,输出$1$或者输出$a,a=b$

CF757B

给定$A=\{a_1,a_2,…,a_n\}$最大化$|S|$其中$S=\{a_{b1},a_{b2},…,a_{bn}\},(a_{b2},…,a_{bn}) \neq 1$

枚举$d$即可

线性求逆元

顺推

1
2
3
4
for(inv[1]=1,i=2;i<=n;i++)
{
inv[i]=(p-p/i)*inv[p%i]%p;
}

倒推

用exgcd求出$inv(n!)$

然后根据$((k-1)!)^{-1}\equiv k\times(k!)^{-1}~(\mod p)$

得到$inv(1!),inv(2!),…,inv((n-1)!)$

方程变形,得到$k^{-1}\equiv(k-1)!\times(k!)^{-1}(\mod p)$

即可求得$[1,n]$逆元

例题

组合数取模,即求得$C(n,k)\% 998244353$,多数询问,$k,n\leq 10^{7}$

预处理,展开即可

线性同余方程

形如$ax \equiv c(\mod b)$的柿子,有解的条件为$(a,b)|c$,若$a\perp b$ 那么就有一个唯一解$x\equiv a^{-1}c(\mod b)$

推论:任意线性同余方程可以判断为无解或者唯一解这样的形式

解方程组

考虑对若干同余方程组联立的方程组求解

考虑中国剩余定理

中国剩余定理

对$x\equiv a_i(\mod{m_i})$若$\forall m_i\perp \forall m_j(i\neq j)$有在$\mod M=\Pi m_i$情况下有唯一解

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
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

//#define register

using namespace std;

const int maxn=20;

int n,tot=1;

int m[maxn],p[maxn];

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

inline int crt()
{
int i;
for(i=1;i<=n;i++) tot*=p[i];
int x,y,t,ans=0;
for(i=1;i<=n;i++)
{
t=tot/p[i];
exgcd(p[i],t,x,y);
ans=(ans+y*t*m[i])%tot;
}
if(ans>0) return ans;
else return ans+tot;
}

signed main()
{
ios::sync_with_stdio(false);
register int i,j;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>p[i]>>m[i];
}
cout<<crt()<<endl;
}

组合数取模2(exLucas)

刚才的组合数取模,不保证$k$是质数$n,k\leq 10^{18}$

使用卢卡斯

$\huge {C_n^m\equiv C_{n\%p}^{m\%p}*C_{n/p}^{m/p}(mod ~p)}$

然后将k分解质因数,后面通过中国剩余定理合并即可

欧拉函数

image-20200723152407044

求欧拉函数$\phi=\Pi(p_i-1)$

例题

SDOI 2012 Longge的问题

求$\large\sum\limits^{n}_{i=1}(i,n),n\leq 2^{32}$

枚举约数即可

SDOI 2008 沙拉公主的疑惑

询问$\large\sum\limits^{n!}_{i=1}(m!\perp i)$

$m,n\leq 10^{7}$多组询问

$ans=(\frac{n!}{m!})*(\phi(m!))$

展开$\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(\frac{1}{p_k})$

$ans=n!(1-\frac{1}{p1})*(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$

$n!$和剩下的都可以线性时间处理

证明欧拉定理

参见费马小定理证明,这东西只需要证明这个双射一一对应即可

有关拓展欧拉定理

image-20200723153443914

image-20200723153708392

image-20200723153949320

费马小定理

image-20200723154158567

这东西咋按这个顺序讲啊

好怪啊

Miller_Rabin

image-20200723154337289

image-20200723154548833

原根

image-20200723154641619

$ord(j)=\phi(m)$

image-20200723154824791

image-20200723154957638

素数都有原根,$3$是$998244353$的原根​

线性筛

image-20200723155500519

image-20200723155835973

例题

image-20200723155938141

赏析

image-20200723160051975

反过来也是,记得处理$x=y$的情况

答案为$2(\phi(1)+…+\phi(?))$

image-20200723160207051

image-20200723160506591

因此线筛即可

image-20200723160540664

这个比较简单

image-20200723160730946

image-20200723161127323

image-20200723161537869

image-20200723161622200

CMSS 20200725

主题:DP

image-20200725145305785

CF1366F