yukicoder : No.1899 L1 Cafe

これは思いつけて良かった。
https://yukicoder.me/problems/no/1899

問題

整数N,A,Bが与えられる。
2次元座標上で、非負整数n,mを用いてx=n*A、y=m*Bと表現できる直線が引かれている。
この直線をたどって原点から移動可能な格子点のうち、正座標でかつ原点からのマンハッタン距離がN以下のものはいくつあるか。

解法

マンハッタン距離がN以下のもののうち、縦線上にある格子点の数と、横線上にある格子点の数から、両線の交点に当たる点の数を引くと解になる。
それぞれの数は、floor_sumを用いて計算できる。

int T;
ll N,A,B;

ll floor_sum(ll N,ll M,ll A,ll B) {
	// sum(i=0...N-1) floor((A*i+B)/M)
	
	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;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		ll ret=0;
		
		ll ma=N,mi=ma%A;
		ret+=floor_sum(ma/A,1,A,N%A);
		ret+=floor_sum(ma/B,1,B,N%B);
		ret-=floor_sum(ma/A,B,A,N%A);
		cout<<ret<<endl;
	}
}

まとめ

floor_sum思いついてよかった。