SPOJ

suffix.cxx

#include <bits/stdc++.h>

using namespace std;

using llint = long long;

int divisors[37];

map<int, pair<llint, llint>> rems;

void eratosten()
{
	int k, i;
	for (k = 2; k <= 36; ++k) if (!divisors[k])
	{
		divisors[k] = k;
		for (i = k * k; i <= 36; i += k)
			divisors[i] = k;
	}
}

llint fmul(llint a, llint b, llint mod = 1ll<<62)
{
	if (a == 0 || b == 0)
		return 0;
	if (a == 1)
		return b % mod;
	if (b == 1)
		return a % mod;
	
	llint ret = fmul((2 * a) % mod, b / 2, mod);
	if (b % 2)
	{
		ret += a;
		ret %= mod;
	}
	return ret;
}

llint fpow(llint a, int b, llint mod = 1ll<<62)
{
	if (b == 0 || a == 1)
		return 1;
	if (a == 0 || b == 1)
		return a;
	
	llint ret = fpow(fmul(a, a, mod), b / 2, mod);
	if (b % 2)
	{
		ret *= a;
		ret %= mod;
	}
	
	return ret;
}

void add(int base, int pw, llint rem)
{
	while (base != 1)
	{
		int d = divisors[base], pwi;
		for (pwi = 0; base % d == 0; ++pwi)
			base /= d;
		
		llint mod = fpow(d, pwi * pw);
		
		if (rems[d].first < mod)
			rems[d] = make_pair(mod, rem % mod);
	}
}

llint inv(int x, int p, int mod)
{
	return fpow(x, mod / p * (p - 1) - 1, mod);
}

llint kineski()
{
	llint ret = 0, N = 1, tmp;
	
	for (auto thing: rems)
		N *= thing.second.first;
	
	//cout<<endl<<N<<endl<<endl;
	
	for (auto thing: rems)
	{
		int p = thing.first;
		llint mod, rem;
		tie(mod, rem) = thing.second;
		/*
		cout<<"Prime: "<<p<<endl;
		cout<<"Mod: "<<mod<<endl;
		cout<<"Rem: "<<rem<<endl;
		cout<<"N / mod: "<<N / mod<<endl;
		cout<<"Inverse: "<<inv(N / mod % mod, p, mod)<<endl;
		*/
		tmp = rem;
		//cout<<"0: "<<tmp<<endl;
		tmp = fmul(tmp, N / mod, N);
		//cout<<"1: "<<tmp<<endl;
		tmp = fmul(tmp, inv(N / mod % mod, p, mod), N);
		//cout<<"2: "<<tmp<<endl;
		
		//cout<<endl;
		
		ret += tmp;
		ret %= N;
	}
	
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	eratosten();
	
	int n;
	
	int base;
	string suff;
	llint rem;
	
	cin>>n;
	
	while (n--)
	{
		cin>>base>>suff;
		rem = stoll(suff, nullptr, base);
		
		add(base, suff.size(), rem);
	}
	
	//cout<<endl;
	//for (auto x: rems)
	//	cout<<x.first<<' '<<x.second.first<<' '<<x.second.second<<endl;
	
	cout<<kineski()<<endl;
}