“虽然我们相差甚远，但至少初心是一致的。”
同余
定义
$a$ 与 $b$ 同余，当且仅当 $a$ 与 $b$ 除以 $p$ 的余数相同，记作 $a$ 与 $b$ 模 $p$ 同余，写作 $a \equiv b \pmod p$。
同余的性质
若 $a \equiv b \pmod p$ ，则有 $a+c \equiv b+c \pmod p$
若 $a \equiv b \pmod p$ ，则有 $ac \equiv bc \pmod p$
若 $a \equiv b \pmod p$ ，且 $c \equiv d \pmod p$ ，则有 $a \pm c \equiv b \pm d \pmod p$
若 $ac \equiv bc \pmod p$ ，且 $(c,m)=1$ ，那么 $a \equiv b \pmod p$
若 $a \equiv b \pmod p$ ，且 $c \equiv d \pmod p$ ，则有 $ac \equiv bd \pmod p$
若 $a \equiv b \pmod p$ ，则有 $ac \equiv bc \pmod {pc}$
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数， $d$ 是 $a,b,m$ 中任一公因数，则如果 $a \equiv b \pmod m$ 成立时，则有 $\frac{a}{d} \equiv \frac{b}{d} \pmod {\frac{p}{d}}$
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数，且 $d|m$，则如果 $a \equiv b \pmod m$ 成立时，则有 $a \equiv b \pmod d$ 。
若 $a$ 和 $b$ 都是整数，且 $d$ 和 $m$ 都是正整数，如果 $a \equiv b \pmod m$ 成立时，则有 $(a,m)=(b,m)$ ，且若如果 $d$ 能够整除 $a,b,m$ 中的任意一个， $d$ 也就能整除 $a,b$ 中的另一个。
扩展欧几里得算法
若 $(a,b)=d$ ，那么对于方程 $ax+by=d$ 的解有一组特殊解为 $x=x_0,y=y_0$ ，那么该方程的通解为 $x=x_0+\frac{b}{d}\times t,y=y_0-\frac{a}{d}\times t$ ，而我们用这个通解来逆向推出 $gcd$ ，因为我们有欧几里得定理：
$(a,b)=d$ ，则有 $(b,a \bmod b)=d$
那么就会推出： $d=a\times y_1+b\times (x_1-y_1\times\frac{a}{b})$
在这个算式中满足： $x=y_1,y=x_1-\frac{a}{b}\times y_1$
扩欧解同余方程
对于方程 $ax \equiv 1 \pmod b$ ，已知 $a$ 与 $b$ ，求出最小的 $x$ 。
LuoguP1082
妥妥的扩欧模板题：
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
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
LL a,b,x,y;
inline void underExgcd(LL a,LL b)
{
if(!b)
{
x=1,y=7;
return ;
}
underExgcd(b,a%b);
LL tx=x;
x=y;
y=tx-a/b*y;
}
int main()
{
underRead(a),underRead(b);
underExgcd(a,b);
x=(x%b+b)%b;
printf("%lld",x);
return 0;
}
|
中国剩余定理
LuoguP1495曹冲养猪
有一个同余方程组满足：
，求出最小的 $x$ 。
思路
设 $M=m_1m_2m_3…m_k$ ，令 $M_i=\frac{M}{m_i}$ ，$t_i$ 是 $M_i$ 的逆元，有 $M_it_i \equiv 1 \pmod m_i$
则 $x=\sum_{i=1}^{k}{a_iM_it_i}$
则可构造特殊解 $x_0=x+k\times M$
最小正整数解即为 $x_{min}=x_0 \bmod M$
P3868 AC Code
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
63
64
65
66
67
68
69
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long LL;
using namespace std;
const int MAXN=1e5+1;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int N;
struct Node
{
LL type,mod;
}Num[MAXN];
LL M[MAXN],Mul=1,Mi[MAXN],X;
inline void underExgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1,y=0;
return ;
}
underExgcd(b,a%b,x,y);
LL z=x;x=y;y=z-y*(a/b);
}
int main()
{
underRead(N);
for(int i=1;i<=N;++i)
{
underRead(Num[i].type),underRead(Num[i].mod);
Mul*=Num[i].type;
}
for(int t=1;t<=N;++t)
{
Mi[t]=Mul/Num[t].type;
LL x=0,y=0;
underExgcd(Mi[t],Num[t].type,x,y);
X+=Num[t].mod*Mi[t]*(x<0?x+Num[t].type:x);
}
printf("%lld",X%Mul);
return 0;
}
|