結果

問題 No.187 中華風 (Hard)
ユーザー batasanblog
提出日時 2025-04-24 22:30:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 789 ms / 3,000 ms
コード長 4,978 bytes
コンパイル時間 6,953 ms
コンパイル使用メモリ 332,876 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-24 22:30:20
合計ジャッジ時間 15,537 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//using mint = modint;
using mint=static_modint<1000000007>;
//istream &operator>>(istream &i,mint &m){int x;i>>x;m=x;return i;}
using ll=long long;
using ull=unsigned long long;
using pl=pair<ll,ll>;
using vl=vector<ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);++i)
#define reps(i,s,n) for(ll i=(s);i<(ll)(n);++i)
#define rep1(i,n) for(ll i=1;i<=(ll)(n);++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define be(v) (v).begin(),(v).end()
const ll INF = 4e18;
template <typename T>
void check_range(T&w,auto&&a,const source_location& l){
	if(a<0||a>=(ll)w.size()){
		cerr<<"OORange! line "<<l.line()<<" col "<<l.column()<<" index "<<a<<" size "<<w.size()<<" func "<<l.function_name()<<endl;
		assert(false);
	}
}
template <typename T>
decltype(auto) at(T&w,auto&&a,const source_location& l=source_location::current()){
	check_range(w,a,l); // if slower, delete it.
	return w[a];
}
template <typename T>
decltype(auto) at(T&w,auto&&a,auto&&b,const source_location& l=source_location::current()){
	return at(at(w,a,l),b,l);
}
template <typename T>
decltype(auto) at(T&w,auto&&a,auto&&b,auto&&c,const source_location& l=source_location::current()){
	return at(at(w,a,b,l),c,l);
}
template <typename T>
decltype(auto) at(T&w,auto&&a,auto&&b,auto&&c,auto&&d,const source_location& l=source_location::current()){
	return at(at(w,a,b,c,l),d,l);
}
template <typename T>
decltype(auto) at(T&w,pl&a,const source_location& l=source_location::current()){
	return at(w,a.fi,a.se,l);
}
#ifdef DEBUG
#include <debug.hpp>
#endif

ll N;
vl X,Y;
void input(){
	cin>>N;
	X.resize(N);
	Y.resize(N);
	rep(n,N)cin>>at(X,n)>>at(Y,n);
}
#ifdef DEBUG
void showall(){
	show(N);
	show("X",X);
	show("Y",Y);
}
#endif
// list up prime factors , Soinsu Bunkai, Yakusu
vector<pl> prime_factor_pair(ll n){
	vector<pl> ret;
	for(ll i=2;i*i<=n;++i){
		ll tmp=0;
		while(n%i==0){
			++tmp;
			n /= i;
		}
		if(tmp>0)ret.eb(i,tmp);
	}
	if(n!=1)ret.eb(n,1);
	return ret;
}
/**
int main(){
	auto pf = prime_factor_pair(N);
	vl divs;
	divisors(1, 0, pf, divs);
**/
// End of prime_number.hpp
const vl MODS={998244353,1107296257,2113929217,1000000007};
inline long long mod(long long a, long long m) {
    long long res = a % m;
    if (res < 0) res += m;
    return res;
}

// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long &p, long long &q) {
    if (b == 0) { p = 1; q = 0; return a; }
    long long d = extGCD(b, a%b, q, p);
    q -= a/b * p;
    return d;
}

// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
    long long x, y;
    extGCD(a, m, x, y);
    return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}


long long Garner(vector<long long> b, vector<long long> m, long long MOD) {
    m.push_back(MOD); // banpei
    vector<long long> coeffs((int)m.size(), 1);
    vector<long long> constants((int)m.size(), 0);
    for (int k = 0; k < (int)b.size(); ++k) {
        long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
        for (int i = k+1; i < (int)m.size(); ++i) {
            (constants[i] += t * coeffs[i]) %= m[i];
            (coeffs[i] *= m[k]) %= m[i];
        }
    }
    return constants.back();
}

// a[k]=m[0]m[1]m[2]...m[k-1]
// b[k]=t[0]+t[1]*m[0]+...+t[k-1]m[0]m[1]...m[k-2]
ll garner(vl&rs,vl ms,ll mod){
	ms.pb(mod);
	vl a(ms.size(),1),b(ms.size(),0);
#ifdef DEBUG
	show("garner",rs,ms,mod);
#endif
	rep(k,rs.size()){
		ll mk=at(ms,k);
		ll t=at(rs,k)-at(b,k);
		t*=inv_mod(at(a,k),mk);
		t=(t%mk+mk)%mk;
		reps(i,k+1,ms.size()){
			ll mi=at(ms,i);
			at(b,i)=(at(b,i)+t*at(a,i))%mi;
			at(a,i)=(at(a,i)*mk)%mi;
		}
#ifdef DEBUG
		show("k",k,"t",t);
		show(" a",a);
		show(" b",b);
#endif
	}
	return b.back();
}
ll logic(){
	mint lcm=1;
	rep(i,N)rep(j,i){
		auto g=gcd(at(Y,i),at(Y,j));
		if((at(X,i)-at(X,j))%g!=0){
			cout<<-1<<endl;
			return 0;
		}
	}
	map<ll,pl>mp;
	rep(n,N){
		auto y=at(Y,n);
		auto pf=prime_factor_pair(y);
		for(auto[a,b]:pf){
			if(mp[a].fi<b)mp[a]=pl(b,n);
		}
	}
	for(auto[k,v]:mp){
		rep(i,v.fi)lcm*=k;
	}
	rep(n,N){
		auto&y=at(Y,n);
		auto pf=prime_factor_pair(y);
		for(auto[a,b]:pf){
			if(mp[a]==pl(b,n))continue;
			rep(i,b)y/=a;
			at(X,n)%=y;
		}
	}
	bool all_zero=true;
	rep(n,N)if(at(X,n)!=0)all_zero=false;
	if(all_zero){
		cout<<lcm.val()<<endl;
		return 0;
	}
	#ifdef DEBUG
	show("X",X);
	show("Y",Y);
	show("mp",mp);
	cerr << "--- Answer ---" << endl;
	#endif
	mint ans=garner(X,Y,mint::mod());
	cout<<ans.val()<<endl;
	//ll ans=Garner(X,Y,mint::mod());
	//cout<<ans<<endl;
	return 1;
}
int main(){
	input();
	#ifdef DEBUG
	showall();
	cerr << "--- Logic ---" << endl;
	#endif
	logic();
	//cout<<logic()<<endl;
	//if(logic())cout<<"Yes"<<endl;
	//else cout<<"No"<<endl;
	//while(input())logic();
	return 0;
}
//cout << fixed << setprecision(16);
0