kmjp's blog

競技プログラミング参加記です

AtCoder ABC #443 (デンソークリエイトプログラミングコンテスト2026) : G - Another Mod of Linear Problem

GよりFに苦戦…。
https://atcoder.jp/contests/abc443/tasks/abc443_g

問題

正整数N,M,A,Bが与えられる。
N要素の整数列Xを、X[k] = (Ak+B) % M としたとき、X[k]>kとなるkはいくつか。

解法

X[k]>kであるには、floor((Ak+B)/M)+1= floor((Ak+B+M-k-1)/M)であればよい。
そこでfloor_sum(N,M,A-1,M+B-1)-floor_sum(N,M,A,B)を答えればよい。

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

template<class V> V floor_sum(V N,V M,V A,V B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	if(A<0) return floor_sum(N,M,-A,B+(N-1)*A); //Aが負の場合傾きを逆にする
	
	V ret=0;
	if(B>=M) ret+=N*(B/M), B%=M;
	if(A>=M) ret+=N*(N-1)/2*(A/M), A%=M;
	
	V Y=(A*N+B)/M;
	if(Y==0) return ret;
	//floor(Y/M)に達するX
	V 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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M>>A>>B;
		
		ll le=floor_sum<__int128>(N,M,A,B);
		ll ok=floor_sum<__int128>(N,M,A-1,M+B-1);
		cout<<ok-le<<endl;
		
	}
}

まとめ

いかにもfloor_sum使えって感じの問題。