OUPC2012 問題D Four Arithmetic Operations (AOJ2353)

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2353）

制約条件

n≦10^5
-10^6≦yi≦10^6
最後の答えは-2^31以上2^31未満の整数になる

方針

最後の答えが-2^31以上2^31未満の整数になることが保証されているので、
適当に大きな素数pを選び、pを法とした余りで計算をすればよい。

pが大きいとp^2が2^64を超えて、long longをオーバーフローする可能性があるので、
JavaでBigIntegerを使うか、適当に素数を二つ選んで、それぞれで計算して中国剰余定理で合成するなどする。

ソースコード

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll g=a; x=1; y=0;
	if(b)g=extgcd(b,a%b,y,x), y-=a/b*x;
	return g;
}
ll inv(ll a,ll m){
	ll x,y;
	extgcd(a,m,x,y);
	return (x%m+m)%m;
}

const int m1=999979,m2=999983;

int main(){
	int n,o,y;
	ll a=0,b=0;
	cin>>n;
	rep(i,n){
		cin>>o>>y;
		if(o==1)a=(a+y)%m1, b=(b+y)%m2;
		if(o==2)a=(a-y%m1+m1)%m1, b=(b-y%m2+m2)%m2;
		if(o==3)a=(a*y)%m1, b=(b*y)%m2;
		if(o==4)a=(a*inv(y,m1))%m1, b=(b*inv(y,m2))%m2;
	}
	ll p,q;
	extgcd(m1,m2,p,q);
	ll ans=(b*m1*p+a*m2*q)%((ll)m1*m2);
	if(ans>=1ll<<31)ans-=(ll)m1*m2;
	cout<<ans<<endl;
	return 0;
}