AtCoder ARC #111 : E - Simple Math 3

思い出せてよかった。
https://atcoder.jp/contests/arc111/tasks/arc111_e

問題

整数A,B,C,Dが与えられる。
A+B*i以上A+C*i以下の整数にDの倍数が現れないようなiは何通りか。

解法

(C-B)*i≧D-1となるiでは必ずDの倍数が1個以上登場するので、それ未満のiについて考える。
iの上限をmとする。
以下の2つの式を考える。

• f(x)=A+C*x
• g(x)=(A-1)+B*x

1≦x≦mで、g(x)＜y≦f(x)であるyにDの倍数が含まれないようなxの数を数え上げたい。
これは、f(x)以下にあるDの倍数とg(x)以下にあるDの倍数の個数が一致しないxを数え上げる問題となる。
そこで、ACLに含まれるfloor_sumを使い、上記を数え上げよう。

ll floor_sum(ll N,ll M,ll A,ll B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	
	if(A<=0) return 0;
	
	ll ret=0;
	if(B>=M) ret+=N*(B/M), B%=M;
	if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M;
	
	ll Y=(A*N+B)/M;
	if(Y==0) return ret;
	//floor(Y/M)に達するX
	ll X=Y*M-B;
	//Xの右側はY個ずつ
	ret+=(N-(X+A-1)/A)*Y;
	// 90度回転、Y=Nのラインは無視する
	ret+=floor_sum(Y,A,M,(A-X%A)%A);
	return ret;
}

int T;
ll A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D;
		int ma=0;
		for(i=29;i>=0;i--) {
			if(1LL*(C-B)*(ma+(1<<i))<D) ma+=1<<i;
		}
		
		ll ret=floor_sum(ma+1,D,C,A)-floor_sum(ma+1,D,B,A-1);
		cout<<ma-ret<<endl;
		
	}
	
}

まとめ

ここでACL出してくるかー、という感想。