SRM523 Div1 Easy - CountingSeries
問題
a+bx、c*d^y (0<=x,y) という形の少なくとも片方で表せるm以下の正の整数の個数を求める
1 <= a,b,c,m <= 10^12
1 <= d <= 10^5
解法
2^40≒10^12だからc*d^yの方はdが2以上ならすぐ全通り試せる
a+bxで表せるm以下の数字の個数を(m-a)/b+1で求めてからc*d^yを一個ずつ見ていき、その数がa+bxで表せない数なら答えを+1
数字pがa+bxで表せるとき、a+bx = p ∴ x = (p-a)/b を満たす非負整数xが存在する
∴ p-a>=0 かつ (p-a)がbで割り切れる
これを満たさない場合のみ答えを+1すればいい
実装
dが1の場合はc*d^y = cだから特別扱いしてやる必要がある
あとif(cd>m)と書くとc=d=10^10、m=10^12みたいなときにオーバーフローするからc>m/dと書いて対策
class CountingSeries { public: ll countThem(ll a, ll b, ll c, ll d, ll m) { ll res = (a<=m ? (m-a)/b + 1 : 0); if (d==1) return res + (c<=m && !(c-a>=0 && (c-a)%b==0)); while (c<=m) { if (!(c-a>=0 && (c-a)%b==0)) res++; if (c>m/d) break; c *= d; } return res; } };