Codeforces #1021 : Div1 C. Bermuda Triangle

これは方針はすぐ立った。
https://codeforces.com/contest/2097/problem/C

問題

(0,0),(0,n),(n,0)の三点で囲まれた三角形領域を考える。
今、座標(x,y)から速度(vx,vy)で点が等速直線運動を行う。その際、三角形の境界にぶつかると、入射角と反射角が一致するように向きを変える。
点が三角形の頂点に到達することはあるか、あるのであれば何回反射するかを求めよ。

解法

点が反射するのを考えるのは面倒なので、三角形領域を境界で鏡像反転させ、領域を埋めることを考える。
反射を無視して、整数k,lを用いて(x,y)→(kn,ln)となる点に移動するケースを考える。
k,lは中国人剰余定理の要領で求めることができる。
その際、三角形を反転させてできた境界線を何回跨ぐかを求めればよい。

int T;
ll N,X,Y,VX,VY;


template<class V> V ext_gcd(V p,V q,V& x, V& y) { // get px+qy=gcd(p,q)
	if(q==0) return x=1,y=0,p;
	V g=ext_gcd(q,p%q,y,x);
	y-=p/q*x;
	return g;
}

template<class V> V rev(V p,V m) { // get p*rev(p)=1 mod m
	assert(__gcd(p,m)==1);
	ll a,b;
	assert(ext_gcd(p,m,a,b)==1);
	a=(a+m)%m;
	return a;
}


template<class V> pair<V,V> crt(V a1,V mo1,V a2,V mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2
	V g,x,y,z;
	g=ext_gcd(mo1,mo2,x,y);
	a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2;
	if(a1%g != a2%g) return pair<V,V>(-1,0); // N/A
	V lcm=mo1*(mo2/g);
	if(lcm<mo1) return pair<V,V>(-2,0); // overflow
	
	V v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g);
	return make_pair(((v%lcm)+lcm) % lcm,lcm);
}

ostream& operator<<(ostream& os, __int128 v) {
	if(v==0) {
		return (os<<'0');
	}
	if(v<0) {
		os<<'-';
		v=-v;
	}
	
	string T;
	while(v) {
		T+=(char)('0'+(v%10));
		v/=10;
	}
	reverse(ALL(T));
	return (os<<T);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y>>VX>>VY;
		
		
		
		ll g=__gcd(VX,VY);
		VX/=g;
		VY/=g;
		auto px=crt<__int128>(0LL,N,X,VX);
		auto py=crt<__int128>(0LL,N,Y,VY);
		if(px.first<0||py.first<0) {
			cout<<-1<<endl;
			continue;
		}
		ll a=px.first-X,as=px.second/VX;
		assert(a%VX==0);
		a/=VX;
		a=(a%as+as)%as;
		ll b=py.first-Y,bs=py.second/VY;
		assert(b%VY==0);
		b/=VY;
		b=(b%bs+bs)%bs;
		auto p=crt<__int128>(a,as,b,bs);
		if(p.first<0) {
			cout<<-1<<endl;
			continue;
		}
		__int128 TX=X+VX*p.first;
		__int128 TY=Y+VY*p.first;
		assert(TX%N==0);
		assert(TY%N==0);
		TX/=N;
		TY/=N;
		if(TY<TX) swap(TX,TY);
		__int128 num=TX+TY-2;
		num+=(TX+TY+1)/2;
		num+=(TY-TX+1)/2;
		
		if((TX+TY)%2) num-=2;
		
		cout<<num<<endl;
		
		
		
	}
}

まとめ

点が反射するタイプの題材で、フィールドの方を鏡像反転させる解法は結構好き。