結果

問題 No.187 中華風 (Hard)
ユーザー 沙耶花沙耶花
提出日時 2021-11-03 23:10:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 432 ms / 3,000 ms
コード長 1,770 bytes
コンパイル時間 5,807 ms
コンパイル使用メモリ 266,140 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-21 16:15:03
合計ジャッジ時間 10,890 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
6,816 KB
testcase_01 AC 38 ms
6,940 KB
testcase_02 AC 159 ms
6,944 KB
testcase_03 AC 155 ms
6,948 KB
testcase_04 AC 321 ms
6,944 KB
testcase_05 AC 316 ms
6,944 KB
testcase_06 AC 318 ms
6,940 KB
testcase_07 AC 320 ms
6,944 KB
testcase_08 AC 431 ms
6,940 KB
testcase_09 AC 430 ms
6,944 KB
testcase_10 AC 432 ms
6,940 KB
testcase_11 AC 317 ms
6,944 KB
testcase_12 AC 321 ms
6,940 KB
testcase_13 AC 266 ms
6,944 KB
testcase_14 AC 221 ms
6,944 KB
testcase_15 AC 105 ms
6,940 KB
testcase_16 AC 111 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 34 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 259 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 319 ms
6,940 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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