时限：1000MS

题意很明确，就是让你解一元同余方程组。题目的要求是找出小于等于\(N\)个数。

利用同余方程的性质，可以找到\(X\)的最小值\(x_0\)，同时也知道\(X\equiv t(mod\,m)\),其中\(m\)为\([m_0,m_1,\cdots,m_M]\),根据上面的条件可以得到\(x_0+m*z\leq N\)，然后将z解出来就是要的答案。

#include "iostream"#include "stdio.h"using namespace std;typedef long long LL;LL m[20], r[20];void ext_gcd(LL a, LL b, LL &d, LL& x, LL& y) {    LL res;    if (!b){x = 1; y = 0; d = a;}    else {        ext_gcd(b, a%b, d, y, x);        y -= x*(a/b);    }}LL mod_line(LL a, LL b, LL m, LL& d) {    LL x, y; ext_gcd(a, m, d, x, y);    if (b%d) return -1;    LL e = x*(b/d)%(m/d) + (m/d);    return e%(m/d);}int main(int argc, char const *argv[]){    int T;    LL N, M;    scanf("%d", &T);    while (T--) {        bool flag = false;        scanf("%lld%lld", &N, &M);        for (int i = 0; i < M; i++) scanf("%lld", m+i);        for (int j = 0; j < M; j++) scanf("%lld", r+j);          for (int i = 1; i < M; i++) {            LL d;            LL x0 = mod_line(m[i-1],r[i] - r[i-1], m[i], d);            if (flag || x0 == -1) {flag = true;  break;}            r[i] = x0*m[i-1]+r[i-1];            m[i] = m[i-1]*(m[i]/d);            r[i] %= m[i];        }         if (flag) printf("0\n");        else {            LL t = 0;            if (r[M-1] <= N) t =(N-r[M-1])/m[M-1] + 1;            if (t && r[M-1] == 0) t--;   //去掉解是0的情况            printf("%lld\n", t);        }            }    return 0;}

时限：1000MS

这道题相比上道题就简单多了，直接计算，然后输出最小的。同样注意要是答案是0的时候的输出。

#include "bits/stdc++.h"using namespace std;typedef long long LL;LL m[20], r[20];void ext_gcd(LL a, LL b, LL &d, LL& x, LL& y) {    LL res;    if (!b){x = 1; y = 0; d = a;}    else {        ext_gcd(b, a%b, d, y, x);        y -= x*(a/b);    }}LL mod_line(LL a, LL b, LL m, LL& d) {    LL x, y; ext_gcd(a, m, d, x, y);    if (b%d) return -1;    LL e = x*(b/d)%(m/d) + (m/d);    return e%(m/d);}int main(int argc, char const *argv[]){    int T; LL N;    int Kcase = 0;    scanf("%d", &T);    while (T--) {        bool flag = false;        scanf("%lld", &N);        for (int i = 0; i < N; i++) scanf("%lld", m+i);        for (int j = 0; j < N; j++) scanf("%lld", r+j);          for (int i = 1; i < N; i++) {            LL d;            LL x0 = mod_line(m[i-1],r[i] - r[i-1], m[i], d);            if (flag || x0 == -1) {flag = true;  break;}            r[i] = x0*m[i-1]+r[i-1];            m[i] = m[i-1]*(m[i]/d);            r[i] %= m[i];        }         printf("Case %d: ", ++Kcase);        if (flag) printf("-1\n");        else {            if (r[N-1] == 0) r[N-1] = m[N-1];            printf("%lld\n", r[N-1]);        }    }    return 0;}