結果

問題 No.187 中華風 (Hard)
ユーザー Sugina_Miku_Sugina_Miku_
提出日時 2018-11-26 03:40:03
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 200 ms / 3,000 ms
コード長 6,825 bytes
コンパイル時間 1,521 ms
コンパイル使用メモリ 172,268 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-26 21:35:37
合計ジャッジ時間 5,243 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 156 ms
4,380 KB
testcase_03 AC 152 ms
4,380 KB
testcase_04 AC 200 ms
4,376 KB
testcase_05 AC 199 ms
4,380 KB
testcase_06 AC 200 ms
4,376 KB
testcase_07 AC 200 ms
4,380 KB
testcase_08 AC 140 ms
4,380 KB
testcase_09 AC 141 ms
4,376 KB
testcase_10 AC 142 ms
4,376 KB
testcase_11 AC 200 ms
4,380 KB
testcase_12 AC 200 ms
4,380 KB
testcase_13 AC 58 ms
4,376 KB
testcase_14 AC 59 ms
4,380 KB
testcase_15 AC 153 ms
4,376 KB
testcase_16 AC 155 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 153 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 200 ms
4,376 KB
testcase_23 AC 1 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iomanip>
//#define DEBUG 0

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VB;

#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define UNQ(a) a.erase(std::unique(ALL(a)),a.end());
#define endl "\n"

const LD EPS=1e-10;
const long long INFLL=(LL)(1e9)*(LL)(1e9);
const int INF=1e9+7;

template<class T>
void chmin(T& a, const T b)
{
	if(a>b)
		a=b;
}
template<class T>
void chmax(T& a, const T b)
{
	if(a<b)
		a=b;
}

const LL powLL(const LL p, const LL q)
{
	LL t=1;
	for(int i=0;i<q;i++)
		t*=p;
	return t;
}

template <typename T>
struct has_iter
{
	private:
		template <typename U>
		static constexpr true_type check(typename U::iterator*);
		template <typename U>
		static constexpr false_type check(...);

	public:
		static constexpr bool value = decltype(check<T>(nullptr))::value;
};


template<typename T, typename U = typename T::iterator>
void print(const T& container)
{
		auto&& first=begin(container), last=end(container);
		auto&& back=prev(last);
		for(auto e=first; e!=last; e=next(e))
			cout<<*e<<" \n"[e==back];
}


extern void* enabler;
template<typename Head, typename enable_if<!has_iter<Head>::value>::type*& = enabler>
void print(const Head& head)
{
	cout<<head<<endl;
}

template<> void print<string>(const string& container)
{
	cout<<container<<endl;
}

template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
	cout<<head<<" ";
	print(tail...);
}

template<typename... Args>
void printd(const Args&... args)
{
	#ifdef DEBUG
		print(args...);
	#endif
}

template<typename Head>
void input(Head& head)
{
	cin>>head;
}

template<typename Head, typename... Tail>
void input(Head& head, Tail&... tail)
{
	cin>>head;
	input(tail...);
}

void io_speedup()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec)
{
	for(T& x: vec) is >> x;
	return is;
}


template<typename T, typename U>
istream& operator >> (istream& is, pair<T, U>& t)
{
	is>>t.first>>t.second;
	return is;
}

template<int N, typename... Ts, typename enable_if<N == sizeof...(Ts)-1>::type*& = enabler>
void tuple_in(istream &is, tuple<Ts...> &t)
{
	is>>get<N>(t);
}
template<int N, typename... Ts, typename enable_if<N < sizeof...(Ts)-1>::type*& = enabler>
void tuple_in(istream &is, tuple<Ts...> &t)
{
	is>>get<N>(t);
	tuple_in<N+1, Ts...>(is, t);
}

template<typename... Ts>
istream& operator >> (istream& is, tuple<Ts...>& t)
{
	tuple_in<0, Ts...>(is, t);
	return is;
}


template<typename T, typename U>
ostream& operator << (ostream& os, const pair<T, U>& t)
{
	os<<'('<<t.first<<", "<<t.second<<')';
	return os;
}

template<int N, typename... Ts, typename enable_if<N == sizeof...(Ts)-1>::type*& = enabler>
void tuple_out(ostream &os,const tuple<Ts...> &t)
{
	os<<get<N>(t);
}
template<int N, typename... Ts, typename enable_if<N < sizeof...(Ts)-1>::type*& = enabler>
void tuple_out(ostream &os,const tuple<Ts...> &t)
{
	os<<get<N>(t)<<", ";
	tuple_out<N+1, Ts...>(os, t);
}

template<typename... Ts>
ostream& operator << (ostream& os, const tuple<Ts...>& t)
{
	os<<'(';
	tuple_out<0, Ts...>(os, t);
	os<<')';
	return os;
}

template<typename T>
vector<T> read(int n)
{
	vector<T> t(n);
	cin>>t;
	return t;
}

template<typename T>
T read()
{
	T t;
	cin>>t;
	return t;
}

template<typename Head, typename... Tail>
struct vector_demensions
{
	using type=vector<typename vector_demensions<Tail...>::type>;
};

template<typename Head>
struct vector_demensions<Head> { using type=Head; };

template<typename T>
vector<T> make_vectors(int size, T val)
{
	return vector<T>(size, val);
}

template<typename T=int, typename... Args>
auto make_vectors(int size, Args... tail)
	-> typename vector_demensions<Args..., T>::type
{
	auto val=make_vectors<T>(forward<Args>(tail)...);
	return vector<decltype(val)>(size, val);
}


namespace Garner
{
    /* Garnerのアルゴリズム
    x = mods[i].first mod mods[i].second を満たすxを求める
    https://qiita.com/drken/items/ae02240cd1f8edfc86fd
    */
    using LL = long long;
	LL gcd(const LL a, const LL b)
	{
		return __gcd(a, b);
	}
    LL mod(const LL p, const LL m)
    {
        return (p<0)?(p%m+m):(p%m);
    }
    LL extgcd(const LL a, const LL b, LL &x, LL &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        LL d=extgcd(b, a%b, y, x);
        y-=a/b*x;
        return d;
    }
    LL modinv(const LL a, const LL m)
    {
        //a*x + m*y = gcd(a,m) = 1
        LL x,y;
        extgcd(a, m, x, y);
        return mod(x, m);
    }

	/*
	Garnerの前処理
	modが互いに素になるようにするor解が無いときは-1を返す
	*/
	vector<pair<LL,LL>> normalize(const vector<pair<LL, LL>> &mods)
	{
		vector<pair<LL, LL>> ret(mods);
		for(size_t i=0;i<ret.size();i++)
		for(size_t j=0;j<i;j++)
		{
			LL g=gcd(ret[i].second, ret[j].second);
			if((ret[i].first - ret[j].first)%g != 0) return vector<pair<LL, LL>>(0);
			ret[i].second/=g;
			ret[j].second/=g;
			LL gi = gcd(ret[i].second, g);
			LL gj = g/gi;
			g = gcd(gi, gj);
			while(g != 1)
			{
				gi*=g;
				gj/=g;
				g = gcd(gi, gj);
			}
			ret[i].second*=gi;
			ret[j].second*=gj;
			ret[i].first%=ret[i].second;
			ret[j].first%=ret[j].second;
		}
		return ret;
	}

    LL Garner(const vector<pair<LL, LL>> &mods, const LL m)
    {
        const int n=mods.size();
        vector<LL> modprod(n+1,1);
        vector<LL> p(n+1);
        for(int i=0;i<n;i++)
        {
            LL t=mod((mods[i].first - p[i]) * modinv(modprod[i], mods[i].second), mods[i].second);

            for(int j=i+1;j<n;j++)
            {
                p[j]+=t*modprod[j];
                p[j]%=mods[j].second;
                modprod[j]*=mods[i].second;
                modprod[j]%=mods[j].second;
            }
            p[n]+=t*modprod[n];
            p[n]%=m;
            modprod[n]*=mods[i].second;
            modprod[n]%=m;
        }
        return p[n];
    }

	LL solve(const vector<pair<LL, LL>> &mods, const LL m)
	{
		const vector<pair<LL,LL>> tmp(normalize(mods));
		if(tmp.size() == 0) return -1;
		return Garner(tmp, m);
	}
}



int main()
{
	int n;
	cin>>n;
	vector<PLL> x(n);
	REP(i,n)
		input(x[i].first, x[i].second);
	auto tmp=Garner::normalize(x);
	if(tmp.size()==0) 
	{
		print(-1);return 0;
	}
	LL ans=Garner::Garner(tmp, INF);
	bool f=accumulate(ALL(tmp), true, [](bool f,const PLL &r){return f&=r.first==0;});
	if(f)
	{
		ans=1;
		for(auto&& e:tmp)
			(ans*=e.second)%=INF;
		print(ans);
	}
	else print(ans);
}
0