题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4078
很容易列出方程组,但因为模数并不一定是质数,可能不存在逆元,因此用辗转相除法来消元
每个齿轮一定不会转动超过 \(n\) 下(鸽巢原理),\(dfs\) 统计回代即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 25;
const int INF = 1000000007;
int n, K;
int a[maxn];
int A[maxn][maxn];
int ans;
void Gauss(){
int i, j, k, r;
for(i = 0 ; i < K ; ++i){
r = i;
for(j = i + 1 ; j < K ; ++j)
if(A[j][i]) r = j;
if(A[r][i] == 0) continue;
if(r != i)
for(j = 0 ; j <= K ; ++j) swap(A[i][j], A[r][j]);
for(j = i + 1 ; j < K ; ++j){ //
if(j != i){
while(A[j][i]){ // 辗转相除法消元,避免除法(模代数系统)
int rate = A[i][i] / A[j][i], tmp;
for(k = 0 ; k <= K ; ++k){
tmp = A[j][k];
A[j][k] = ((A[i][k] - rate * A[j][k]) % n + n) % n;
A[i][k] = tmp;
}
}
}
}
}
}
int t[maxn][maxn], val[maxn];
void dfs(int pos, int res){
if(res >= ans) return;
if(pos == -1){
ans = res;
return;
}
for(int i = 0 ; i < K ; ++i){
for(int j = 0 ; j <= K ; ++j){
t[i][j] = A[i][j];
}
}
for(int i = 0 ; i < n ; ++i){
val[pos] = i;
int now = 0;
for(int j = pos ; j < K ; ++j){
now = (now + A[pos][j] * val[j]) % n;
}
if(now % n == A[pos][K] % n) dfs(pos - 1, res + i);
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }
int main(){
while(scanf("%d%d", &K, &n) == 2 && K){
memset(val, 0, sizeof(val));
memset(A, 0, sizeof(A));
int x;
for(int i = 0 ; i < K ; ++i) {
scanf("%d", &x);
A[i][K] = n + 1 - x;
}
int p, u, v;
for(int i = 1 ; i <= K ; ++i){
scanf("%d", &p);
for(int j = 1 ; j <= p ; ++j){
scanf("%d%d", &u, &v);
A[u-1][i-1] = v;
}
}
Gauss();
ans = INF;
dfs(K-1, 0);
if(ans == INF){
printf("No solution\n");
}
else printf("%d\n", ans);
}
return 0;
}