結果
問題 | No.1931 Fraction 2 |
ユーザー |
![]() |
提出日時 | 2022-04-29 14:41:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 3,130 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 209,640 KB |
最終ジャッジ日時 | 2025-01-28 22:18:32 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr int mod = 998244353;long long modpow(long long a,long long b) {long long ans = 1;while(b) {if(b & 1) {(ans *= a) %= mod;}(a *= a) %= mod;b /= 2;}return ans;}long long modpow(long long a,long long b,long long m) {long long ans = 1;while(b) {if(b & 1) {(ans *= a) %= m;}(a *= a) %= m;b /= 2;}return ans;}long long modinv(long long a, long long m) {long long b = m,u = 1,v = 0;while (b) {long long t = a/b;a -= t*b;u -= t*v;swap(a,b);swap(u,v);}u %= m;if (u < 0) {u += m;}return u;}struct primenumber {vector<int> spf;primenumber(int N) {init(N);}void init(int N) {spf.assign(N+1,0);for(int i = 0; i <= N; i++) {spf[i] = i;}for(int i = 2; i*i <= N; i++) {if(spf[i] == i) {for(int j = i*i; j <= N; j += i) {if(spf[j] == j) {spf[j] = i;}}}}}bool is_prime(long long n) {bool flag = true;if(n == 1) {flag = false;}for(long long i = 2; i*i <= n; i++) {if(n%i == 0) {flag = false;break;}}return flag;}map<int,int> get(int n) {map<int,int> m;while(n != 1) {m[spf[n]]++;n /= spf[n];}return m;}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int>A(N),B(N);for(int i = 0; i < N; i++) {cin >> A[i] >> B[i];}primenumber zz(200000);vector<vector<pair<int,int>>>pura(200001);for(int i = 0; i < N; i++) {for(auto j:zz.get(B[i])) {pura[j.first].push_back({j.second,i});}}long long d = 1;for(int i = 2; i <= 200000; i++) {if(pura[i].empty()) {continue;}int mx = 0;for(int j = 0; j < pura[i].size(); j++) {mx = max(mx,pura[i][j].first);}int cnt = 0;vector<long long>tmp(mx);long long gyaku = modpow(i,mx);for(int j = 0; j < pura[i].size(); j++) {tmp[mx-pura[i][j].first] += A[pura[i][j].second]*modinv(B[pura[i][j].second]/modpow(i,pura[i][j].first),gyaku);}long long sum = 0;for(int j = 0; j < mx; j++) {sum += tmp[j];if(sum%i == 0) {sum /= i;cnt++;}else {break;}}d *= modpow(i,mx-cnt);d %= mod;}int c = 0;for(int i = 0; i < N; i++) {c += A[i]*d%mod*modpow(B[i],mod-2)%mod;if(c >= mod) {c -= mod;}}cout << c << " " << d << endl;}