AtCoder ARC #127 : F - ±AB

似たような問題、見たことあるなと思いつつ簡単には解けないよなぁ。
https://atcoder.jp/contests/arc127/tasks/arc127_f

問題

正整数A,B,V,Mが与えられる。
AとBは互いに素とする。
変数xの初期値はVである。
このxに、

• Aを加算
• Bを加算
• Aを減算
• Bを減算

することを繰りかえす。ただし、0≦x≦Mでなければならない。
xが取りうる値は何通りか。

解法

Mが十分に大きく、A+B＜Mならxは任意の値を取れる。
そうでない場合、取りうるパターンは以下のいずれかである。

• xに(Mを超えない範囲で)Aを加算し、その後(0を切らない範囲で)Bを減算し、また(Mを超えない範囲で)Aを加算し…
• xに(Mを超えない範囲で)Bを加算し、その後(0を切らない範囲で)Aを減算し、また(Mを超えない範囲で)Bを加算し…

以下前者だけを考える。その代わり、初期値x=M-Vの時の前者の遷移を考えれば、それはx=Vから始めたときの後者の遷移と同じ遷移を取る。
これ以上遷移できなくなるのはx＜Bかつx+A＞Mの場合である。
Aの加算回数をkとすると、B-1≧(V+kA)%B≧M-A+1となる最小のkまで、Aの加算が可能である。
式変形するとM-A+1-V%B≦(kA%B)≦B-1-V%Bとなるkを求める問題となる。

これは以下のように考えられる。
2次元座標上に、(0,0)-(B,A)を対角線とする矩形を考える。この矩形領域は(RPGのマップのように)トーラス状になっていて上下や左右はつながっている。
ここで(0,0)から(1,1)の向きに線を伸ばし、いつ(M-A+1-V%B,0)-(B-1-V%B,0)の線分と交差するかを求める問題となる。
これは互除法の要領でO(log(A+B))で解くことができる。

int T;
ll A,B,V,M;

ll hoge2(ll L,ll R,ll H,ll W) {
	
	if(L==0) return 0;
	
	ll ma=W/H;
	ll okL=(L+H-1)/H;
	ll okR=R/H;
	if(okL<=okR) {
		return okL;
	}
	else {
		ll p=hoge2((H-R%H)%H,(H-L%H)%H,W%H,H);
		return (L+p*W+H-1)/H;
	}
	
}

ll hoge(ll A,ll B,ll V,ll M) {
	if(V%B>=M-A+1) return 0;
	ll L=M-A+1-V%B;
	ll R=B-1-V%B;
	if(L>R) return 0;
	
	ll k=hoge2(L,R,A,B);
	return k+(k*A+V)/B;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>V>>M;
		if(A+B-1<=M) {
			cout<<(M+1)<<endl;
			continue;
		}
		ll ret=1;
		ret+=hoge(A,B,V,M);
		ret+=hoge(A,B,M-V,M);
		cout<<ret<<endl;
	}
}

まとめ

以前のAGCも似たような解き味の問題があったような。