結果

問題 No.187 中華風 (Hard)
ユーザー 沙耶花
提出日時 2021-11-03 23:10:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 443 ms / 3,000 ms
コード長 1,770 bytes
コンパイル時間 4,995 ms
コンパイル使用メモリ 262,096 KB
最終ジャッジ日時 2025-01-25 11:15:21
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000001

//互いに素なmとその余りrに合致する値をmintで返す
mint Garner(vector<long long> m,vector<long long> r){
	int n = m.size();
/*
	rep(i,n){
		cout<<m[i]<<endl;
	}
	*/
	vector<long long> t(n);
	rep(i,n){
		long long cur = 0LL;
		long long cm = 1LL;
		rep(j,i){
			cur += t[j] * cm;
			cur %= m[i];
			cm *= m[j];
			cm %= m[i];
		}
		cur = r[i] - cur;
		cur %= m[i];
		if(cur<0)cur += m[i];
		
		cur *= inv_mod(cm,m[i]);
		
		cur %= m[i];
		t[i] = cur;
	}
	
	mint ret = 0;
	mint cm = 1;
	rep(i,n){
		ret += cm * t[i];
		cm *= m[i];
	}
	return ret;
	
}

int main(){	
	
	int N;
	cin>>N;
	
	vector<long long> r(N),m(N);
	rep(i,N)cin>>r[i]>>m[i];
	
	map<int,int> mp;
	rep(i,N){
		long long tm = m[i];
		map<int,int> temp;
		for(long long j=2;j*j<=tm;j++){
			while(tm%j==0){
				tm /= j;
				if(temp.count(j)){
					temp[j] *= j;
				}
				else{
					temp[j] = j;
				}
			}
		}
		if(tm!=1)temp[tm] = tm;
		for(auto a:temp){
			mp[a.first] = max(mp[a.first],a.second);
		}
	}
	
	for(auto a:mp){
	//	cout<<a.second<<endl;
		vector<long long> rr,mm;
		rep(i,N){
			long long temp = gcd(m[i],a.second);
			if(temp==1)continue;
			rr.push_back(r[i]%temp);
			mm.push_back(temp);
			m[i] /= temp;
			r[i] %= m[i];
		}
		auto ret = crt(rr,mm);
		if(ret.second==0){
			cout<<-1<<endl;
			return 0;
		}
		r.push_back(ret.first);
		m.push_back(ret.second);
	}
				
	
	if(r==vector<long long>(r.size(),0LL)){
		mint ans = 1;
		for(auto a:mp){
			ans *= a.second;
		}
		cout<<ans.val()<<endl;
	}
	else{
		cout<<Garner(m,r).val()<<endl;
	}
	
	return 0;
	
}
0