結果
問題 | No.2119 一般化百五減算 |
ユーザー |
|
提出日時 | 2022-11-04 22:30:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,096 bytes |
コンパイル時間 | 275 ms |
コンパイル使用メモリ | 34,176 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 20:26:23 |
合計ジャッジ時間 | 1,271 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 19 WA * 6 |
ソースコード
#include <stdio.h>#include <string.h>#include <stdlib.h>#define LOG(FMT...) fprintf(stderr, FMT)const int N = 100005;int n, m, b[N], c[N];int exgcd(int a, int b, int &x, int &y) {if (b) {int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;}x = y = 1;return a;}int main() {scanf("%d%d", &n, &m);for (int i = 0; i < m; ++i) {scanf("%d%d", b + i, c + i);c[i] %= b[i];if (c[i] < 0) {c[i] += b[i];}}int B, C;B = 1, C = 0;for (int i = 0; i < m; ++i) {if (b[i] > B) {B = b[i], C = c[i];}}for (int i = 0; i < m && B < 1000; ++i) {int x, y, d;d = exgcd(B, b[i], x, y);int dc = C - c[i];if (dc % d) {puts("NaN");return 0;}int t = dc / d;x *= t, y *= t;int nb = B * b[i] / d;int nc = (c[i] + y * b[i]) % nb;if (nc < 0) {nc += nb;}B = nb, C = nc;}for (int k = 0, x; (x = k * B + C) < n; ++k) {bool flag = true;for (int i = 0; i < m; ++i) {if (x % b[i] != c[i]) {flag = false;}}if (flag) {printf("%d\n", x);return 0;}}puts("NaN");return 0;}