AtCoder ABC #186 (パナソニックプログラミングコンテスト) : E - Throne

ちょっとFに手間取りすぎた。
https://atcoder.jp/contests/abc186/tasks/abc186_e

問題

N個の椅子が円形に並んでいる。
今玉座から時計回りでS個めの席に座っている人が、1回移動するたびに時計回りでK個先の席に移るとする。
玉座に移るのは何回目の移動後か。

解法

解をaとすると、a*K mod N = (N-S)を求める問題となる。
g=GCD(K,N)とするとき、(N-S)がgで割り切れないなら解なし。
そうでない場合、K'=K/g、N'=N/g、L=(N-S)/gとする。

そうするとa*K'= L (mod N')を求める問題となった。
x*K' + y*N' = 1 の解を拡張ユークリッドの互除法で求めたら、aは(x*L)%Nとなる。

int T;
ll N,S,K;

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S>>K;
		
		ll lef=N-S;
		ll d=__gcd(K,N);
		if(lef%d) {
			cout<<-1<<endl;
		}
		else {
			lef/=d;
			N/=d;
			K/=d;
			ll X,Y;
			ll a=ext_gcd(K,N,X,Y);
			X*=lef;
			X=(X%N+N)%N;
			cout<<X<<endl;
			
		}
		
	}
}

まとめ

ACL使ったら速かったりするのかな。