こういうのさっと詰められないんだよな…。
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)を経由するってのは覚えておくとよさそう。