結果
問題 | No.1931 Fraction 2 |
ユーザー |
|
提出日時 | 2022-04-27 22:26:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 583 ms / 2,000 ms |
コード長 | 1,792 bytes |
コンパイル時間 | 5,375 ms |
コンパイル使用メモリ | 257,840 KB |
最終ジャッジ日時 | 2025-01-28 22:05:18 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using i64=long long;using u64=unsigned long long;using namespace std;template<u64 mod> using modint=atcoder::static_modint<mod>;struct primefact{int n;vector<i64> lpf;primefact(int n_):n(n_),lpf(n_+1,-1){for(i64 p=2;p<=n;++p){if(lpf[p]!=-1){continue;}lpf[p]=p;for(i64 q=p;q<=n;q+=p){if(lpf[q]==-1){lpf[q]=p;}}}}vector<pair<i64,i64>> operator()(int m){vector<i64> v;while(m!=1){v.emplace_back(lpf[m]);m/=lpf[m];}if(v.size()==0){return {};}vector<pair<i64,i64>> res;res.emplace_back(v[0],1);for(size_t i=1;i<v.size();++i){if(v[i-1]!=v[i]){res.emplace_back(v[i],1);}else{res.back().second++;}}return res;}};int main(){constexpr u64 mod=998244353;typedef modint<mod> mint;primefact pf(300'001);int N;cin>>N;vector<i64> A(N),B(N);vector<vector<pair<i64,i64>>> idx(300'001);vector<i64> m(300'001);mint sm=0;for(int i=0;i<N;++i){cin>>A[i]>>B[i];sm+=mint(A[i])/B[i];auto tmp=pf(B[i]);for(auto [p,e]:tmp){idx[p].emplace_back(i,e);m[p]=max(m[p],e);}}mint d=1;for(i64 p=2;p<=300'001;++p){if(m[p]==0){continue;}vector<i64> pw(21,1);for(int i=1;i<=20;++i){pw[i]=pw[i-1]*p;}i64 sm=0;for(auto [i,e]:idx[p]){sm+=A[i]*pw[m[p]-e]*atcoder::inv_mod(B[i]/pw[e],pw[m[p]]);sm%=pw[m[p]];}i64 prd=pw[m[p]];for(int i=0;i<m[p];++i){if(sm%p==0){sm/=p;prd/=p;}else{break;}}d*=prd;}cout<<(sm*d).val()<<" "<<d.val()<<endl;}