結果
問題 | No.187 中華風 (Hard) |
ユーザー |
|
提出日時 | 2024-11-14 12:45:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,574 bytes |
コンパイル時間 | 3,998 ms |
コンパイル使用メモリ | 300,196 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 12:46:02 |
合計ジャッジ時間 | 10,679 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 WA * 14 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const ll MOD = (ll)(1e9 + 7);template <typename T = ll>T ext_gcd(T a, T b, T& x, T& y) {x = 1; y = 0;T x1 = 0, y1 = 1, a1 = a, b1 = b;while (b1) {T q = a1 / b1;tie(x, x1) = make_tuple(x1, x - q * x1);tie(y, y1) = make_tuple(y1, y - q * y1);tie(a1, b1) = make_tuple(b1, a1 - q * b1);}return a1;}template <typename T = ll>vector<T> garner(vector<T> a, vector<T> m) {int k = a.size();for (int i = 0; i < k; i++) {a[i] = (a[i] % m[i] + m[i]) % m[i];}vector<T> x(k);for (int i = 0; i < k; i++) {x[i] = a[i];for (int j = 0; j < i; j++) {T tmp, r;ext_gcd(m[i], m[j], tmp, r);x[i] = (r * (x[i] - x[j]) % m[i] + m[i]) % m[i];}}return x;}template <typename T = ll>bool crt_general(vector<T> a, vector<T> m, vector<T>& ans, vector<T>& radix) {int k = a.size();map<T, pair<T, T>> mp;for (int i = 0; i < k; i++) {T tmp = m[i];for (T j = 2; j * j <= tmp; j++) {if (tmp % j == 0) {T res = 1;while (tmp % j == 0) {tmp /= j; res *= j;}T ap = (a[i] % res + res) % res;if (mp.contains(j)) {if (mp[j].second < res) {swap(mp[j].first, ap);swap(mp[j].second, res);}if (mp[j].first % res != ap) {return false;}} else {mp[j] = make_pair(ap, res);}}}if (tmp > 1) {T ap = (a[i] % tmp + tmp) % tmp;if (mp.contains(tmp)) {if ((mp[tmp].first - ap) % tmp) {return false;}} else {mp[tmp] = make_pair(ap, tmp);}}}vector<T> na, nm;for (auto it = mp.begin(); it != mp.end(); it++) {na.push_back(it->second.first);nm.push_back(it->second.second);}radix = nm;ans = garner(na, nm);return true;}ll mod_lcm(int n, vector<ll> y) {map<int, ll> pfs;for (int i = 0; i < n; i++) {for (int j = 2; j * j <= y[i]; j++) {if (y[i] % j == 0) {ll pf = 1;while (y[i] % j == 0) {y[i] /= j; pf *= j;}if (pfs.contains(j)) {pfs[j] = max(pfs[j], pf);} else {pfs[j] = pf;}}}if (y[i] > 1 && !pfs.contains(y[i])) {pfs[y[i]] = y[i];}}ll ret = 1;for (auto it = pfs.begin(); it != pfs.end(); it++) {ret = ret * it->second % MOD;}return ret;}int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);int n; cin >> n;vector<ll> a(n), m(n);for (int i = 0; i < n; i++) {cin >> a[i] >> m[i];}vector<ll> ans, radix;if (crt_general(a, m, ans, radix)) {ll res = 0, prod = 1;for (int i = 0; i < n; i++) {res = (res + ans[i] * prod) % MOD;prod = prod * radix[i] % MOD;}if (res > 0) cout << res << "\n";else cout << mod_lcm(n, m) << "\n";} else {cout << -1 << "\n";}return 0;}