結果
| 問題 |
No.1931 Fraction 2
|
| コンテスト | |
| ユーザー |
 tokusakurai
|
| 提出日時 | 2022-05-06 22:58:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,904 bytes |
| コンパイル時間 | 3,345 ms |
| コンパイル使用メモリ | 212,444 KB |
| 最終ジャッジ日時 | 2025-01-29 04:01:57 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 WA * 4 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, x, n) for (int i = x; i <= n; i++)
#define rep3(i, x, n) for (int i = x; i >= n; i--)
#define each(e, v) for (auto &e : v)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
template <typename T>
bool chmax(T &x, const T &y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T>
bool chmin(T &x, const T &y) {
return (x > y) ? (x = y, true) : false;
}
template <typename T>
int flg(T x, int i) {
return (x >> i) & 1;
}
template <typename T>
void print(const vector<T> &v, T x = 0) {
int n = v.size();
for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
if (v.empty()) cout << '\n';
}
template <typename T>
void printn(const vector<T> &v, T x = 0) {
int n = v.size();
for (int i = 0; i < n; i++) cout << v[i] + x << '\n';
}
template <typename T>
int lb(const vector<T> &v, T x) {
return lower_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, T x) {
return upper_bound(begin(v), end(v), x) - begin(v);
}
template <typename T>
void rearrange(vector<T> &v) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
template <typename T>
vector<int> id_sort(const vector<T> &v, bool greater = false) {
int n = v.size();
vector<int> ret(n);
iota(begin(ret), end(ret), 0);
sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; });
return ret;
}
template <typename S, typename T>
pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) {
return make_pair(p.first + q.first, p.second + q.second);
}
template <typename S, typename T>
pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) {
return make_pair(p.first - q.first, p.second - q.second);
}
template <typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &p) {
S a;
T b;
is >> a >> b;
p = make_pair(a, b);
return is;
}
template <typename S, typename T>
ostream &operator<<(ostream &os, const pair<S, T> &p) {
return os << p.first << ' ' << p.second;
}
struct io_setup {
io_setup() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << fixed << setprecision(15);
}
} io_setup;
const int inf = (1 << 30) - 1;
const ll INF = (1LL << 60) - 1;
// const int MOD = 1000000007;
const int MOD = 998244353;
template <int mod>
struct Mod_Int {
int x;
Mod_Int() : x(0) {}
Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
static int get_mod() { return mod; }
Mod_Int &operator+=(const Mod_Int &p) {
if ((x += p.x) >= mod) x -= mod;
return *this;
}
Mod_Int &operator-=(const Mod_Int &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
Mod_Int &operator*=(const Mod_Int &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
Mod_Int &operator/=(const Mod_Int &p) {
*this *= p.inverse();
return *this;
}
Mod_Int &operator++() { return *this += Mod_Int(1); }
Mod_Int operator++(int) {
Mod_Int tmp = *this;
++*this;
return tmp;
}
Mod_Int &operator--() { return *this -= Mod_Int(1); }
Mod_Int operator--(int) {
Mod_Int tmp = *this;
--*this;
return tmp;
}
Mod_Int operator-() const { return Mod_Int(-x); }
Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }
Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }
Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }
Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }
bool operator==(const Mod_Int &p) const { return x == p.x; }
bool operator!=(const Mod_Int &p) const { return x != p.x; }
Mod_Int inverse() const {
assert(*this != Mod_Int(0));
return pow(mod - 2);
}
Mod_Int pow(long long k) const {
Mod_Int now = *this, ret = 1;
for (; k > 0; k >>= 1, now *= now) {
if (k & 1) ret *= now;
}
return ret;
}
friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; }
friend istream &operator>>(istream &is, Mod_Int &p) {
long long a;
is >> a;
p = Mod_Int<mod>(a);
return is;
}
};
using mint = Mod_Int<MOD>;
struct Random_Number_Generator {
mt19937_64 mt;
Random_Number_Generator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
int64_t operator()(int64_t l, int64_t r) { // [l,r) で乱数発生
uniform_int_distribution<int64_t> dist(l, r - 1);
return dist(mt);
}
int64_t operator()(int64_t r) { // [0,r) で乱数発生
return (*this)(0, r);
}
} rng;
long long modpow(long long x, long long n, const int &m) {
x %= m;
long long ret = 1;
for (; n > 0; n >>= 1, x *= x, x %= m) {
if (n & 1) ret *= x, ret %= m;
}
return ret;
}
template <typename T>
T modinv(T a, const T &m) {
T b = m, u = 1, v = 0;
while (b > 0) {
T t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return u >= 0 ? u % m : (m - (-u) % m) % m;
}
template <typename T>
T Euler_totient(T m) { // オイラーの φ 関数（x と m が互いに素ならば、x^φ(m) ≡ 1(mod m)）
T ret = m;
for (T i = 2; i * i <= m; i++) {
if (m % i == 0) ret /= i, ret *= i - 1;
while (m % i == 0) m /= i;
}
if (m > 1) ret /= m, ret *= m - 1;
return ret;
}
int modlog(int x, int y, int m) { // x^k ≡ y(mod m) となる最小の非負整数 k（存在しなければ -1）
long long g = 1;
for (int i = m; i > 0; i >>= 1) g *= x, g %= m;
g = gcd(g, m);
int c = 0;
long long t = 1;
for (; t % g != 0; c++) {
if (t == y) return c;
t *= x, t %= m;
}
if (y % g != 0) return -1;
t /= g, y /= g, m /= g;
int n = 0;
long long gs = 1;
for (; n * n < m; n++) gs *= x, gs %= m;
unordered_map<int, int> mp;
long long e = y;
for (int i = 0; i < n; mp[e] = ++i) e *= x, e %= m;
e = t;
for (int i = 0; i < n; i++) {
e *= gs, e %= m;
if (mp.count(e)) return c + n * (i + 1) - mp[e];
}
return -1;
}
template <typename T>
T order(T x, const T &m) { // x^k ≡ 1(mod m) となる最小の正整数 k（x と m は互いに素）
T n = Euler_totient(m);
vector<T> ds;
for (T i = 1; i * i <= n; i++) {
if (n % i == 0) ds.push_back(i), ds.push_back(n / i);
}
sort(begin(ds), end(ds));
for (auto &e : ds) {
if (modpow(x, e, m) == 1) return e;
}
return -1;
}
template <typename T>
T primitive_root(const T &m) { // 素数 m の原始根
vector<T> ds;
for (T i = 1; i * i <= m - 1; i++) {
if ((m - 1) % i == 0) ds.push_back(i), ds.push_back((m - 1) / i);
}
sort(begin(ds), end(ds));
while (true) {
T r = rng(1, m);
for (auto &e : ds) {
if (e == m - 1) return r;
if (modpow(r, e, m) == 1) break;
}
}
}
template <typename T>
vector<T> divisors(const T &n) {
vector<T> ret;
for (T i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(begin(ret), end(ret));
return ret;
}
template <typename T>
vector<pair<T, int>> prime_factor(T n) {
vector<pair<T, int>> ret;
for (T i = 2; i * i <= n; i++) {
int cnt = 0;
while (n % i == 0) cnt++, n /= i;
if (cnt > 0) ret.emplace_back(i, cnt);
}
if (n > 1) ret.emplace_back(n, 1);
return ret;
}
template <typename T>
bool is_prime(const T &n) {
if (n == 1) return false;
for (T i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
// 1,2,...,n のうち k と互いに素である自然数の個数
template <typename T>
T coprime(T n, T k) {
vector<pair<T, int>> ps = prime_factor(k);
int m = ps.size();
T ret = 0;
for (int i = 0; i < (1 << m); i++) {
T prd = 1;
for (int j = 0; j < m; j++) {
if ((i >> j) & 1) prd *= ps[j].first;
}
ret += (__builtin_parity(i) ? -1 : 1) * (n / prd);
}
return ret;
}
vector<bool> Eratosthenes(const int &n) {
vector<bool> ret(n + 1, true);
if (n >= 0) ret[0] = false;
if (n >= 1) ret[1] = false;
for (int i = 2; i * i <= n; i++) {
if (!ret[i]) continue;
for (int j = i + i; j <= n; j += i) ret[j] = false;
}
return ret;
}
vector<int> Eratosthenes2(const int &n) {
vector<int> ret(n + 1);
iota(begin(ret), end(ret), 0);
if (n >= 0) ret[0] = -1;
if (n >= 1) ret[1] = -1;
for (int i = 2; i * i <= n; i++) {
if (ret[i] < i) continue;
for (int j = i + i; j <= n; j += i) ret[j] = min(ret[j], i);
}
return ret;
}
int main() {
int N;
cin >> N;
int M = 200000;
auto ps = Eratosthenes2(M);
vector<int> a(N), b(N);
vector<vector<vector<int>>> ids(M + 1, vector<vector<int>>(20));
rep(i, N) {
cin >> a[i] >> b[i];
int x = b[i];
int pre = -1, cnt = 1;
while (x > 1) {
int t = ps[x];
if (t != pre) {
if (pre != -1) ids[pre][cnt].eb(i);
pre = t, cnt = 1;
} else {
cnt++;
}
x /= t;
}
if (pre != -1) ids[pre][cnt].eb(i);
}
mint x = 1; // 分母
rep2(i, 2, M) {
int K = -1;
rep(j, 20) {
if (!empty(ids[i][j])) chmax(K, j);
}
if (K == -1) continue;
vector<ll> pw(K + 1, 1);
rep(j, K) pw[j + 1] = pw[j] * i;
rep3(j, K, 1) { // 分母 i^j としたとき分子は i で割り切れるか
ll s = 0;
rep3(k, K, j) {
ll tmp = 0;
each(e, ids[i][k]) {
ll A = a[e], B = b[e] / pw[k];
B = modpow(B, pw[k - j] * (i - 1) - 1, pw[k - j + 1]);
A *= B, A %= pw[k - j + 1];
tmp += A;
tmp %= pw[k - j + 1];
}
s += tmp / pw[k - j];
s %= i;
}
if (s > 0) {
x *= mint(i).pow(j);
break;
}
}
}
mint ans = 0;
rep(i, N) ans += mint(a[i]) / mint(b[i]);
cout << ans * x << ' ' << x << '\n';
}