AOJ 2353: Four Arithmetic Operations

気がついたら簡単だった。
二つの1000000より大きい素数modで答えを求めてから二つのmodどちらにも当てはまるものを答えるだけ(中国剰余定理から当たり前)
負が入力に入るのがちょっと厄介。

だけど、どうやってデータセットを作っているのだろう。気になる。多倍長でがんばってるんだろうか。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod1=1000033;
long long mod2=1000037;
long long inv(long long x,int t){
	long long ret=1;
	long long now=x;
	long long mod=mod1;
	if(t==2)mod=mod2;
	int pow=mod-2;
	while(pow){
		if(pow%2){
			ret=ret*now%mod;
		}
		now=now*now%mod;
		pow/=2;
	}
	return ret;
}
int main(){
	int a;
	scanf("%d",&a);
	long long v1=0;
	long long v2=0;
	for(int i=0;i<a;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		if(p==1){
			v1=(v1+mod1+q%mod1)%mod1;
			v2=(v2+mod2+q%mod2)%mod2;
		}
		if(p==2){
			v1=(v1+mod1-q%mod1)%mod1;
			v2=(v2+mod2-q%mod2)%mod2;
		}
		if(p==3){
			v1=(v1*(q%mod1+mod1))%mod1;
			v2=(v2*(q%mod2+mod2))%mod2;
		}
		if(p==4){
			v1=(v1*inv((q%mod1+mod1),1))%mod1;
			v2=(v2*inv((q%mod2+mod2),2))%mod2;
		}
	}
	//printf("%lld %lld\n",v1,v2);
	for(long long x=-1000000;x<=1000000;x++){
		long long N=x*mod1+v1;
		long long M=(N%mod2+mod2)%mod2;
		if(M==v2&&-(1LL<<31)<=N&&N<(1LL<<31)){
			printf("%lld\n",N);return 0;
		}
	}
}