AtCoder ARC #149 : F - Rational Number System

ボス問にしては実装は短いけど、考察は難しい。
https://atcoder.jp/contests/arc149/tasks/arc149_f

問題

整数P,Q,N,L,Rが与えられる。
1～NをP/Q進数表記したものを辞書順に並べたとき、L番目からR番目に来る値を求めよ。

解法

P/Q進数表記したとき、数Aに対しA*(P/Q)+Rと表現される数に対しA→(A*(P/Q)+R)と辺を張ったTrieを考える。
1～Nの整数は、このTrieをBFSする順番で現れる。
また辞書順で並べるということは、このTrieをDFS順に訪問する整数値を並べることに相当する。

そこでこのTrieをDFSし、L番目からR番目に到達するものを求めよう。

ll P,Q,N,L,R;

__int128 hoge(__int128 L,__int128 R) {
	if(L==0) L++;
	R=min(R,(__int128)N);
	if(R<L) return 0;
	__int128 sum=R-L+1;
	
	L=(L+Q-1)/Q*P;
	R=R/Q*P+P-1;
	return sum+hoge(L,R);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P>>Q>>N>>L>>R;
	ll num=R-L;
	L++;
	
	__int128 cur=0;
	vector<ll> V;
	while(1) {
		L--;
		if(L==0) break;
		assert(cur%Q==0);
		ll a=cur/Q*P;
		ll b=cur/Q*P+(P-1);
		for(i=60;i>=0;i--) if(hoge(a,b-(1LL<<i))>=L) b-=(1<<i);
		
		L-=hoge(a,b-1);
		V.push_back(b-a);
		cur=b;
	} 
	
	cout<<(ll)cur<<endl;
	
	while(num--) {
		if(cur%Q==0&&cur/Q*P<=N) {
			V.push_back(0);
			cur=cur/Q*P;
		}
		else {
			while(V.back()==P-1||cur+1>N) {
				V.pop_back();
				cur=cur/P*Q;
			}
			V.back()++;
			cur++;
		}
		cout<<(ll)cur<<endl;
		
	}
}

まとめ

辞書順に並べる＝Trie DFS順に並べる、という言い換え意外と使わない？