SRM 523 div1 easy:CountingSeries

問題

TopCoder Statistics - Problem Statement

解法

やるだけ問題です。

基本的に a と b を使うタイプのやつは割り算で ub 以下のものの個数を求めて, c と d を使うタイプのものは ub 以下のものを全列挙します。で, 全列挙したものの中で ab タイプと被るものがあったら答えから減らしていきます。

class CountingSeries {
public:
    long long countThem(long long a, long long b, long long c, long long d, long long ub) {
        if (d == 1) {
            if (ub >= a) {
                ll ans = (ub-a)/b+1;
                ans++;
                if ((c-a)%b == 0 && c >= a && c <= ub) ans--;
                else if (c > ub) ans--;
                return ans;
            } else {
                if (c <= ub) return 1;
                else return 0;
            }
        } else {
            set<ll> S;
            ll now = c;
            while (now <= ub) {
                S.insert(now);
                now *= d;
            }
            ll ans = 0;
            if (ub >= a) {
                ans = (ub-a)/b+1;
            }
            ans += S.size();
            for (ll el : S) {
                if ((el-a)%b == 0 && el >= a) ans--;
            }
            return ans;
        }
    }
};