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;
		}
};