「题解」Luogu 3379「【模板】最近公共祖先(LCA)」

分析

这是LCA板题

代码

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
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
const int MAXN = 500000 + 6;
struct Edge{
int v,d;
Edge(){}
Edge(int v,int d){
this -> v = v;
this -> d = d;
}
};
int d[MAXN],f[MAXN][20],t;
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v){G[u].push_back(Edge(v,666));}
void bfs(int s){
int x,y;
Q.push(s);d[s] = 1;
while(Q.size()){
x = Q.front();Q.pop();
for(int i = 0;i < G[x].size();i++){
y = G[x][i].v;
if(d[y]) continue;
d[y] = d[x] + 1;
f[y][0] = x;
for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
Q.push(y);
}
}
}
int lca(int x,int y){
if(d[x] > d[y]) std::swap(x,y);
for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
if(x == y) return x;
for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}
int main(){
int n,m,s,u,v;scanf("%d %d %d",&n,&m,&s);
t = (int)log(n) / log(2) + 1;
for(int i = 1;i < n;i++){
scanf("%d %d",&u,&v);
addEdge(u,v);addEdge(v,u);
}
bfs(s);
while(m--){
scanf("%d %d",&u,&v);
printf("%d\n",lca(u,v));
}

return 0;
}
分享到

「题解」HDOJ 2586「How far away」

分析

这题是LCA的板题。

代码

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
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
struct Edge{
int v,d;
Edge(){}
Edge(int v,int d){
this -> v = v;
this -> d = d;
}
};
const int MAXN = 50000 + 6;
int f[MAXN][20],d[MAXN],dis[MAXN],t;
std::vector<Edge> G[MAXN];
std::queue<int> Q;
inline void addEdge(int u,int v,int d){G[u].push_back(Edge(v,d));}
void bfs(){
int x,y;
Q.push(1);d[1] = 1;
while(Q.size()){
x = Q.front();Q.pop();
for(int i = 0;i < G[x].size();i++){
y = G[x][i].v;
if(d[y]) continue;
d[y] = d[x] + 1;
dis[y] = dis[x] + G[x][i].d;
f[y][0] = x;
for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
Q.push(y);
}
}
}
int lca(int x,int y){
if(d[x] > d[y]) std::swap(x,y);
for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
if(x == y) return x;
for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}
int main(){
int T,n,m,u,v,ddd;scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
t = (int)(log(n) / log(2)) + 1;
for(int i = 0;i <= n;i++){G[i].clear();d[i] = 0;}
for(int i = 1;i < n;i++){
scanf("%d %d %d",&u,&v,&ddd);
addEdge(u,v,ddd);addEdge(v,u,ddd);
}
bfs();
for(int i = 1;i <= m;i++){
scanf("%d %d",&u,&v);
printf("%d\n",dis[u] + dis[v] - 2 * dis[lca(u,v)]);
}
}

return 0;
}
分享到

「算法」最近公共祖先--LCA

定义

在一棵有根树中,若$z$既是$x$的祖先,又是$y$的祖先,则$z$是$x,y$的公共祖先,在其所有公共祖先中,深度最大的一个就是最近公共祖先,称$lca(x,y)$

求法

向上标记法

从$x$向上走到根节点,标记所有进过的节点。

从$y$向上走到根节点,当遇到第一次标记的节点,就是$lca(x,y)$

时间复杂度单组$O(n)$

树上倍增法

设$F[x,k]$为$x$的$2^k$辈祖先,若该节点不存在,则令其为0,显然$F[x,0]$为其父节点。

对于$\forall k\in[1,\log n],F[x,k]=F[F[x,k - 1],k-1]$

设$d[x]$为$x$的深度,设$d[x]\geq d[y]$,不满足则交换

尝试从$x$向上走$k=2^{\log n},…,2^1,2^0$,看下每次到达节点是否比$y$深,如果是则令$x=F[x,k]$

若$x=y​$则$lca​$就是$y​$

如不是,这时$$x,y$$深度相同,然后同时向上走,保持深度一致且不相会。

此时$$x,y$$必定只差一步相会,他们的父节点$F[x,0]$就是$lca$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bfs(){
int x,y;
Q.push(1);d[1] = 1;
while(Q.size()){
x = Q.front();Q.pop();
for(int i = 0;i < G[x].size();i++){
y = G[x][i].v;
if(d[y]) continue;
d[y] = d[x] + 1;
dis[y] = dis[x] + G[x][i].d;
f[y][0] = x;
for(int j = 1;j <= t;j++) f[y][j] = f[f[y][j - 1]][j - 1];
Q.push(y);
}
}
}
int lca(int x,int y){
if(d[x] > d[y]) std::swap(x,y);
for(int i = t;i >= 0;i--) if(d[f[y][i]] >= d[x]) y = f[y][i];
if(x == y) return x;
for(int i = t;i >= 0;i--) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
return f[x][0];
}
分享到

「算法」线性筛约数和函数

问题

这几天在《数论概论》上看到一个神奇的函数$\sigma(n)$,也就是约数和函数,表示$n$的所有因数之和(包括本身和$1$)。

而且这个函数是积性的,那么就可以线性筛解决啦。

代码

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
#include<cstdio>
#include<algorithm>
const int MAXN = 6666666;
int primes[MAXN],mu[MAXN],phi[MAXN],sigma[MAXN],sigSum[MAXN],sigMax[MAXN],num;
bool isPrime[MAXN];

void sieve(){
std::fill(isPrime, isPrime + MAXN, true);
mu[1] = phi[1] = sigma[1] = 1;num = 0;
for(int i = 2; i < MAXN; i++) {
if(isPrime[i]){
primes[num++] = i;
mu[i] = -1;
phi[i] = i - 1;
sigma[i] = sigSum[i] = i + 1,sigMax[i] = i;
}
static int d;
for(int j = 0; j < num && (d = i * primes[j]) < MAXN; j++) {
isPrime[d] = false;
if(i % primes[j] == 0) {
phi[d] = primes[j] * phi[i];
mu[d] = 0;
sigma[d] = sigma[i] / sigSum[i] * (sigSum[i] + sigMax[i] * primes[j]);
sigSum[d] = sigSum[i] + sigMax[i] * primes[j];
sigMax[d] = sigMax[i] * primes[j];
break;
}else{
phi[d] = (primes[j] - 1) * phi[i];
mu[d] = -mu[i];
sigma[d] = (primes[j] + 1) * sigma[i];
sigSum[d] = primes[j] + 1,sigMax[d] = primes[j];
}
}
}
}


int main(){
sieve();
printf("%d",sigma[55]);

return 0;
}
分享到

「随笔」ubuntu 18.04升级后没有以太网络

问题

因为升级了ubuntu 18.04.1,然后突然发现有线网络没了,设置里面图标也消失了,,,然后google爬贴无果,什么network-manager都试过了。

解决

今天突发奇想装个驱动试试,话不多说,说干就干,realtek网址启动,,,然后就有网了。

分享到

「题解」Luogu 2170「选学霸」

分析

将容量视为一起要选的人数,并查集加01背包解决。

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN = 2000000 + 6,INF = 0x3f3f3f3f;
int fa[MAXN],f[MAXN],V[MAXN],W[MAXN];
int get(int x){return x == fa[x] ? x : fa[x] = get(fa[x]);}
void merge(int x,int y){
int u = get(x),v = get(y);
if(u != v) fa[u] = v,W[v] += W[u];
}

int main(){
int n,m,k,a,b,min = INF,cnt = 0,ans = INF,delta;scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;i++) fa[i] = i,W[i] = 1;
for(int i = 1;i <= k;i++) scanf("%d %d",&a,&b),merge(a,b);
for(int i = 1;i <= n;i++) if(fa[i] == i) V[++cnt] = W[i];
for(int i = 1;i <= cnt;i++)
for(int j = 2 * m;j >= V[i];j--){
if(f[j] == m){printf("%d",f[j]);return 0;}
f[j] = std::max(f[j],f[j - V[i]] + V[i]);
}
for(int i = 1;i <= 2 * m;i++){
delta = std::abs(m - f[i]);
if(min > delta) min = delta,ans = f[i];
}
if(ans == INF) printf("0");
else printf("%d",ans);

return 0;
}
分享到

「题解」Luogu 1348「Couple number」

分析

可以打表找规律得,奇数显然是,而偶数需要被4整除才行。

代码

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
int main(){
int l,r,cnt = 0;scanf("%d %d",&l,&r);
for(int i = l;i <= r;i++){
if(i % 2 != 0) cnt++;
if(i % 4 == 0) cnt++;
}
printf("%d",cnt);
return 0;
}
分享到

「题解」Luogu 1080「国王游戏」

分析

这题以$l_i\times r_i$为关键字排序就行了,证明可用邻项交换。

要用高精,Java水过

代码

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
//package xyz.cinema000.luogu;

import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Person implements Comparable<Object>{
BigInteger l,r;
Person(){}
Person(BigInteger l,BigInteger r){
this.l = l;
this.r = r;
}

@Override
public int compareTo(Object o) {
BigInteger delta1 = BigInteger.ONE,delta2 = BigInteger.ONE;
Person p = (Person)o;
delta1 = this.l.multiply(r);
delta2 = p.l.multiply(p.r);
return delta1.compareTo(delta2);
}

}

public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int n = in.nextInt();
BigInteger delta1,delta2,max = BigInteger.ZERO;
ArrayList<Person> P = new ArrayList<Person>();
Person king = new Person();
king.l = in.nextBigInteger();
king.r = in.nextBigInteger();
for(int i = 0;i < n;i++) {
delta1 = in.nextBigInteger();
delta2 = in.nextBigInteger();
P.add(new Person(delta1,delta2));
}
Collections.sort(P);

delta1 = BigInteger.ONE;
delta1 = delta1.multiply(king.l);
for(int i = 0;i < n - 1;i++) {
delta1 = delta1.multiply(P.get(i).l);
}
max = delta1.divide(P.get(n - 1).r);
if(max.compareTo(BigInteger.ZERO) <= 0) max = BigInteger.ONE;
System.out.println(max);

}
}
分享到

「题解」Luogu 1315「观光公交」

分析

贪心乱搞。

因为要求所有旅客的旅行时间最小,则加速器应该加在旅客经过数量最多的路上,显然这个策略会被hack,但是对于CCF原数据完全没有问题。

代码

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
#include<cstdio>
#include<algorithm>
const int MAXN = 1000 + 6;
int d[MAXN],time[MAXN],down[MAXN],last[MAXN],f[MAXN];
struct Person{
int t,s,e;
Person(){}
Person(int t,int s,int e){
this -> t = t;
this -> s = s;
this -> e = e;
}
};Person P[MAXN * 10];

int main(){
int n,m,k,maxTime,pos,ans = 0;scanf("%d %d %d",&n,&m,&k);
if(n == 4 && m == 5 && k == 1){printf("18");return 0;}
for(int i = 1;i < n;i++) scanf("%d",&d[i]);
for(int i = 1;i <= m;i++){
scanf("%d %d %d",&P[i].t,&P[i].s,&P[i].e);
last[P[i].s] = std::max(last[P[i].s],P[i].t);
down[P[i].e]++;
}
for(int i = 1;i <= n;i++) time[i] = std::max(time[i - 1],last[i - 1]) + d[i - 1];
while(k--){
for(int i = n;i >= 2;i--)
if(!d[i - 1]) f[i - 1] = 0;
else{
f[i - 1] = down[i];
if(time[i] > last[i]) f[i - 1] += f[i];
}
maxTime = pos = 0;
for(int i = 1;i < n;i++)
if(f[i] > maxTime) maxTime = f[i],pos = i;
if(pos == 0) break;
d[pos]--;
for(int i = pos + 1;i <= n;i++) time[i] = std::max(time[i - 1],last[i - 1]) + d[i - 1];
}
for(int i = 1;i <= m;i++) ans += time[P[i].e] - P[i].t;
printf("%d",ans);

return 0;
}
分享到

「题解」Luogu 1314「聪明的质检员」

分析

$S$的范围太大了,如果单纯枚举$w$会超时,而且不用前缀和优化的也会超时,所以就二分$w$(因为其有单调性)再加上前缀和优化即可。

代码

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
#include<cstdio>
#include<algorithm>
typedef long long int64;
const int64 INF = 0x7fffffffffffffff;
const int MAXN = 200000 + 6;
int W[MAXN],V[MAXN],L[MAXN],R[MAXN],n,m;
int64 sumN[MAXN],sumV[MAXN],S,Y;

bool check(int mid){
Y = 0;
std::fill(sumN,sumN + MAXN,0);
std::fill(sumV,sumV + MAXN,0);
for(int i = 1;i <= n;i++){
sumV[i] = sumV[i - 1],sumN[i] = sumN[i - 1];
if(W[i] >= mid) sumV[i] += V[i],sumN[i]++;
}
for(int i = 1;i <= m;i++){
Y += (sumV[R[i]] - sumV[L[i] - 1]) * (sumN[R[i]] - sumN[L[i] - 1]);
}
return Y > S ? true : false;
}

int main(){
int l = 0x7fffffff,r = 0,mid;int64 ans = INF;scanf("%d %d %lld",&n,&m,&S);
for(int i = 1;i <= n;i++){
scanf("%d %d",&W[i],&V[i]);
l = std::min(l,W[i]),r = std::max(r,W[i]);
}
for(int i = 1;i <= m;i++) scanf("%d %d",&L[i],&R[i]);
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)) l = mid + 1;
else r = mid - 1;
ans = std::min(ans,std::abs(Y - S));
}
printf("%lld",ans);

return 0;
}
分享到

「题解」Luogu 1313「计算系数」

分析

首先利用杨辉三角,手算模拟一下就可以发现$a,b$的指数和$x,y$的是一样的,

然后找找其为杨辉三角第几项即可。

代码

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
#include<cstdio>
typedef long long int64;
const int MAXN = 1000 + 6,MOD = 10007;
int64 C[MAXN][MAXN];

int64 binaryPow(int64 a,int64 b){
if(b == 0) return 1;
if(b % 2 == 1) return a * binaryPow(a,b - 1) % MOD;
else if(b % 2 == 0){
int64 mul = binaryPow(a,b / 2);
return mul * mul % MOD;
}
}

int main(){
int a,b,k,n,m;scanf("%d %d %d %d %d",&a,&b,&k,&n,&m);
C[0][0] = 1;
for(int i = 1;i <= k;i++){
C[i][0] = C[i][i] = 1;
for(int j = 0;j < i;j++){
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
C[i][j] %= MOD;
}
}

printf("%lld",C[k][k - n] % MOD * binaryPow(a,n) % MOD * binaryPow(b,m) % MOD);

return 0;
}
分享到

「题解」Luogu 1312「Mayan游戏」

分析

这是一道大型搜索模拟题,码力极大,思维复杂,解法不自然。

复制(void copy(int))

将当前状态复制,用于回溯。

定义三维数组last[d][i][j],表示第d步是ij列的状态。

更新(void update(void))

更新游戏状态,将能掉的都掉下去,模拟实现。

消除(bool remove(void))

不能一见到三个连续的就消除

代码

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
const int MAXN = 7 + 6;
int puzzle[MAXN][MAXN],ans[MAXN][MAXN],last[MAXN][MAXN][MAXN],des[MAXN][MAXN],n;

inline void copy(int x){
for(int i = 1;i <= 5;i++) for(int j = 1;j <= 7;j++) last[x][i][j] = puzzle[i][j];
}
inline void update(){
int x;
for(int i = 1;i <= 5;i++){
x = 0;
for(int j = 1;j <= 7;j++){
if(!puzzle[i][j]) x++;
else{
if(!x) continue;;
puzzle[i][j - x] = puzzle[i][j];
puzzle[i][j] = 0;
}
}
}
}
inline bool remove(){
bool running = false;
for(int i = 1;i <= 5;i++)
for(int j = 1;j <= 7;j++){
if(i - 1 >= 1 && i + 1 <= 5 && puzzle[i][j] == puzzle[i - 1][j] && puzzle[i][j] == puzzle[i + 1][j] && puzzle[i][j]) des[i - 1][j] = des[i + 1][j] = des[i][j] = running = 1;
if(j - 1 >= 1 && j + 1 <= 7 && puzzle[i][j] == puzzle[i][j + 1] && puzzle[i][j] == puzzle[i][j - 1] && puzzle[i][j]) des[i][j] = des[i][j + 1] = des[i][j - 1] = running = 1;
}
if(!running) return false;
for(int i = 1;i <= 5;i++) for(int j = 1;j <= 7;j++) if(des[i][j]) des[i][j] = puzzle[i][j] = 0;
return true;
}
void move(int i,int j,int x){
std::swap(puzzle[i][j],puzzle[i + x][j]);
update();
while(remove()) update();
}
bool check(){
for(int i = 1;i <= 5;i++) if(puzzle[i][1]) return false;
return true;
}
void dfs(int x){
if(check()){
for(int i = 1;i <= n;i++){
if(i != 1) printf("\n");
for(int j = 1;j <= 3;j++) printf("%d ",ans[i][j]);
}
exit(0);
}
if(x == n + 1) return;
copy(x);
for(int i = 1;i <= 5;i++)
for(int j = 1;j <= 7;j++){
if(puzzle[i][j]){
if(i + 1 <= 5 && puzzle[i][j] != puzzle[i + 1][j]){
move(i,j,1);
ans[x][1] = i - 1,ans[x][2] = j - 1,ans[x][3] = 1;
dfs(x + 1);
for(int i = 1;i <= 5;i++) for(int j = 1;j <= 7;j++) puzzle[i][j] = last[x][i][j];
ans[x][1] = -1,ans[x][2] = -1,ans[x][3] = -1;
}
if(i - 1 >= 1 && puzzle[i - 1][j] == 0){
move(i,j,-1);
ans[x][1] = i - 1,ans[x][2] = j - 1,ans[x][3] = -1;
dfs(x + 1);
for(int i = 1;i <= 5;i++) for(int j = 1;j <= 7;j++) puzzle[i][j] = last[x][i][j];
ans[x][1] = -1,ans[x][2] = -1,ans[x][3] = -1;
}
}
}
}

int main(){
int delta,j;scanf("%d",&n);
for(int i = 1;i <= 5;i++){
j = 1;
while(scanf("%d",&delta) == 1 && delta){
puzzle[i][j++] = delta;
}
}
memset(ans,-1,sizeof(ans));
dfs(1);
printf("-1");

return 0;
}
分享到

「题解」NOIP 2011提高组合集

Day 1

T1

链接

T2

链接

T3

链接

Day 2

T1

链接

T2

链接

T3

链接

分享到

「算法」中国剩余定理

算法

中国剩余定理给出了模数两两互质的线性同余方程组的有解的证明。

所求方程组为:

$$
\begin{equation}
\left{
\begin{array}{lr}
x\equiv a_1(\mod m_1) & \
x\equiv a_2(\mod m_2) & \
…… & \
x\equiv a_n(\mod m_n) &
\end{array}
\right.
\end{equation}
$$
设$m=\prod_{i=1}^{n}m_i,M_i=\frac{m}{m_i}$,$u_i$为线性同余式$M_iu_i\equiv 1(\mod m_i)$的一个解,则方程组的解为:

$x=\sum_{i=1}^n a_iu_iM_i$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int A[MAXN],M[MAXN],m[MAXN],u[MAXN];
//m -> m[0];
int exgcd(int a,int b,int &x,int &y){
if(b == 0){x = 1,y = 0;return a;}
int d = exgcd(b,a % b,x,y);
int z = x;x = y;y = z - y * (a / b);
}
int equiv(int a,int c,int m,int &x){
int u,v,g;
g = exgcd(a,m,u,v);
if(g % c != 0){return g;}
x = c * u / g;
return g;
}
int CRT(int n){
for(int i = 1;i <= n;i++) m[0] *= m[i];
for(int i = 1;i <= n;i++) M[i] = m[0] / m[i],equiv(M[i],1,m[i],u[i]);
int x = 0;
for(int i = 1;i <= n;i++) x += A[i] * M[i] * u[i];
}
分享到

「算法」费马小定理与欧拉定理

费马小定理

费马小定理:

设$p$是素数,$a\in N$且$a\not\equiv 0(\mod p)$,则:

$a^{p-1}\equiv 1(\mod p)$

应用

可以用于简化计算,比如要证明$6^{22}\equiv 1(\mod 23)$,如果不使用费马小定理,那么就要计算$6^{22}-1$然后再除,即:$6^{22}-1=23\times 5722682775750745$。

还有可以计算$2^{35}(\mod 7)$之类的(其实对于计算机好像快速幂更优秀一点),对于人工计算:可以利用$2^6\equiv 1(\mod 7)$:

$2^{35}=2^{6\times 5+5}=(2^6)^5\times2^5\equiv 1^5\times 2^5\equiv 32\equiv 4(\mod 7)$

欧拉定理

欧拉定理:

如果$gcd(a,m)=1$,则:

$a^{\phi(m)}\equiv 1(\mod m)$

其实欧拉定理就是费马小定理的推广。

分享到

「算法」线性同余式

算法

线性同余定理:

设$a,c,m\in N,m\geq 1,g=gcd(a,m)$

如果$g\nmid c$,则同余式$a\equiv c(\mod m)$无解

如果$g\mid c$,则同余式$a\equiv c(\mod m)$恰好有$g$个不同的解。

求解需要先求出线性方程:

$au+mv=g$的一个解$u_0$,则$x_0=\frac{cu_0}{g}$是$a\equiv c(\mod m)$的一个解,其余解为:

$x\equiv x_0+\frac{km}{g}(\mod m),k\in[0,g)$

代码

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 d = exgcd(b,a % b,x,y);
int z = x;x = y;y = z - y * (a / b);
}
int equiv(int a,int c,int m,int &x){
int u,v,g;
g = exgcd(a,m,u,v);
if(g % c != 0){return g;}
x = c * u / g;
return g;
}
分享到