結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0