kmjp's blog

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

yukicoder : No.2128 Round up!!

こういうのさっと詰められないんだよな…。
https://yukicoder.me/problems/no/2128

問題

正整数X,A,Bが与えられる。
以下の処理を任意回数任意の順で行える時、Xが取る値は何通りか。

  • Xを、Xを以上で最小のAの倍数で置き換える
  • Xを、Xを以上で最小のBの倍数で置き換える

解法

以下A<Bのケースを考える。
Xに前者・後者の順で処理した値をX(B,A)のように表現する。
まず、同じ処理を2回繰り返してもXは2回目で変化しないので、行うならばX(A,B,A,B...)かX(B,A,B,A....)の2択である。

いずれにしても、X(B,A)の値は経由する。よって、X(B,A)以降はX(A,B,A), X(B,A,B,A)...と続き、XがAとBのLCMになったら打ち止めである。その値をQとする。
X(B,A)→Qに至る処理回数は、A,Bが互いに素なら2(Q-X(B,A)+B)/B通りとなる。
あとは、X(B,A)に至るまでのバリエーションとして、X,X(A),X(B),X(A,B)の値を列挙すればよい。

int T;
ll X_,A_,B_;
__int128 X,A,B;

__int128 F(__int128 x, __int128 v) {
	return (x+v-1)/v*v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X_>>A_>>B_;
		X=X_;
		A=A_;
		B=B_;
		if(A>B) swap(A,B);
		
		
		set<__int128> S;
		S.insert(X);
		S.insert(F(X,A));
		S.insert(F(X,B));
		S.insert(F(F(X,A),B));
		X=F(F(X,B),A);
		S.insert(X);
		
		__int128 ret=0;
		FORR(s,S) if(s<=X) ret++;
		if(X%B==0) {
			cout<<(ll)ret<<endl;
			continue;
		}
		
		__int128 g=__gcd(A,B);
		X/=g;
		A/=g;
		B/=g;
		
		
		auto Q=F(X,A*B);
		
		ret+=2*((Q-X+B)/B)-1;
		cout<<(ll)(ret%998244353)<<endl;
		
	}
}

まとめ

必ずX(B,A)を経由するってのは覚えておくとよさそう。