SRM 523 Div2 Medium CountingSeries

問題

自然数a,b,c,dが与えられた時次の2つの数を考える.a+b*x, c*d^y.x, yも自然数
1からUpperBoundまでの数で上の2つの式で表される数の個数を答えよ.

解答

a+b*xに属する個数はUpperBoundが分かれば即座にわかる.
またある数がa+b*xに属するかも同様に即座にわかる.
なのでc*d^yに属する数を全て求め,a+b*xに属さないものだけ数え上げ.
2つの数え上げを足せば良い.
UpperBoundはすごく大きいかもしれないが,c*d^yの増加傾向もすごく大きいので問題なし.

class CountingSeries {
public:
  long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
    long long res = 0;
    int xi, yi;
    xi = yi = 1;
    long long B = c;
    if(a <= upperBound) res=1 + (upperBound - a) / b;
    if(d == 1 &&
       B <= upperBound &&
       (B < a || (B - a) % b != 0)) res++;
    while(d > 1 && B <= upperBound){
      if (B < a || (B - a) % b != 0) res++;
      // if (B < a || ((B > a) && ((B - a) % b != 0))) res++;
      B *= d;
    }
    return res;
  }