\u2026 n \u5143\u7ebf\u6027\u65b9\u7a0b\u7ec4\u7684\u6c42\u89e3\u2026
\n<\/p>\n
.. (n + 1) \u6b21 exGcd .. \u5224\u65ad\u662f\u5426\u6709\u89e3 ..
\n\u4e4b\u540e\u2026 \u7cfb\u6570\u5411\u91cf\u7528\u521a\u624d\u7684\u4e2d\u95f4\u7ed3\u679c\u53cd\u4ee3\u51fa\u5373\u53ef\u3002<\/p>\n
\r\n#include <iostream>\r\n#include <cmath>\r\n \r\nusing namespace std;\r\n \r\n#define DO(N) while(N--)\r\n#define REP(I, N) for (int I=0;I<int(N);++I)\r\n#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)\r\n#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)\r\n#define FOR_1(I, A, B) for (int I=int(A);I<=int(B);++I)\r\n#define DWN_1(I, B, A) for (int I=int(B);I>=int(A);--I)\r\n \r\ntemplate<class T> inline void RD(T &x){\r\n char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0';\r\n for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';\r\n}\r\ntemplate<class T> inline void RD(T &x0, T &x1){RD(x0), RD(x1);}\r\ntemplate<class T> inline void RD(T &x0, T &x1, T &x2){RD(x0), RD(x1), RD(x2);}\r\n \r\ntypedef long long LL;\r\n \r\nconst int N = 100;\r\nint a[N], x[N], y[N];\r\nint n, b, c, d, t, m, _;\r\n \r\n \r\ninline void INC(int &a, int b){\r\n a += b; if (a >= m) a -= m;\r\n}\r\n \r\ninline void DEC(int &a, int b){\r\n a -= b; if (a < 0) a += m;\r\n}\r\n \r\ninline void MUL(int &a, int b){\r\n a = int(LL(a) * b % m);\r\n}\r\n \r\ninline int mul(int a, int b){\r\n return int(LL(a) * b % m);\r\n}\r\n \r\ninline void exGcd(int m, int n, int &d, int& a, int & b){\r\n\tint xx = 0, yy = 1, x = 1, y = 0, q;\r\n\twhile (true){\r\n\t\tq = m \/ n, m %= n;\r\n if (!m) {d = n, a = xx, b = yy; return;}\r\n\t\tDEC(x, mul(q, xx)), DEC(y, mul(q, yy));\r\n q = n \/ m, n %= m;\r\n if (!n) {d = m, a = x, b = y; return;}\r\n DEC(xx, mul(q, x)), DEC(yy, mul(q, y));\r\n\t}\r\n}\r\n \r\n \r\nvoid init(){\r\n RD(n); REP(i, n) RD(a[i]);\r\n RD(b, m);\r\n \r\n b %= m;\r\n REP(i, n) a[i] %= m;\r\n \r\n}\r\n \r\nvoid solve(){\r\n \r\n d = a[0], --n;\r\n \r\n REP(i, n){\r\n exGcd(d, a[i+1], d, x[i], y[i]); \r\n }\r\n \r\n exGcd(d, m, d, t, _);\r\n \r\n if (b % d) {\r\n printf("NO\\n");\r\n return;\r\n }\r\n \r\n c = b \/ d;\r\n \r\n MUL(c, t), MUL(x[n-1], c), MUL(y[n-1], c);\r\n \r\n DWN(i, n, 1){\r\n x[i+1] = y[i], MUL(x[i-1], x[i]), MUL(y[i-1], x[i]);\r\n }\r\n x[1] = y[0];\r\n \r\n FOR(i, 0, n){\r\n printf("%d ", x[i]);\r\n }\r\n printf("%d\\n", x[n]);\r\n}\r\n \r\n \r\nint main(){\r\n \/\/freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n \r\n int T; RD(T);\r\n DO(T){\r\n init(); solve();\r\n }\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n