c_Comp-Prog yukicoder No.2177 Recurring ab
これめちゃくちゃ好きです 本質部分の問題設定に違和感がないのに独自性が強い(気がする)
問題
正の整数$ Nが与えられる。
$ p進数の$ 0.ababab\dotsとなる循環小数を作るための$ (p,a,b)となる整数の組を用意したとき、
$ \frac{1}{N}より大きくなるものの個数を求めよ。
制約
$ 1 \le N \le 10^8
$ 2 \le p \le 10^9
$ a,b: $ 0.ababab\dotsを$ p進数として扱うことできる数字
考察
まず式に落としてみる。
循環小数の分数化をすると、$ p進数の$ 0.ababab\dotsは$ \frac{ap+b}{p^2-1}となる。(循環小数の繰り返しをする個数が2のため、左シフトを2回して元の数を引く)
よって、$ \frac{ap+b}{p^2-1} > \frac{1}{N}となる$ (p,a,b)を求めれば良い。
$ aと$ bの状態数が少ないことを利用すると、それぞれで二重ループを回して上式を満たす$ pの範囲を考えれば計算量的に良いことがわかる。
また、式を少し整理して$ N > \frac{p^2-1}{ap+b}の形にすると、右辺の式は$ a,bが正であれば$ pに対して単調性を満たすことがわかる。(微分すると理解できる)
そのため、この形で$ a,bを固定して、$ pに対する上式を満たす範囲を求める二分探索を行えばこの問題は$ O(ab\log p)で解くことができた。
実装
code:solve.cpp
int main(){
long long n;cin>>n;
long long ans = 0;
for(long long a = 0; 10 > a; a++){
for(long long b = 0; 10 > b; b++){
if(a==b)continue;
long long mn = max(a,b)+1;
long long mx = 1000000001;
while(mx-mn > 1){
long long ce = (mn+mx)/2;
if(n*(a*ce+b) > ce*ce-1){
mn = ce;
}else{
mx = ce;
}
}
if(n*(a*mn+b) > mn*mn-1)ans += mn-(max(a,b));
}
}
cout << ans << endl;
}
感想
この形の式が単調性を持つ関数に化けるのすごいな...って思いました