SRM523 Div1 Easy(250), Div2 Medium(500) CountingSeries

CountingSeries

等比数列は数が少ないので、等差数列の個数をまず求め、等差数列に含まれない等比数列の要素の個数を加える。
d==1は別扱いしないと処理が終わらないとか、upperBound<aもupperBound<bもありうるとか、d==1を処理するときにc<=upperBoundを確認しないといけないとか、罠が多い。

class CountingSeries{public:
long long countThem( long long a, long long b, long long c, long long d, long long upperBound )
{
    long long ans = 0;

    if ( a<=upperBound )
        ans += (upperBound-a)/b+1;

    for ( long long i=c; i<=upperBound; i*=d )
    {
        if ( i<a || (i-a)%b!=0 )
            ans++;
        if ( d==1 )
            break;
    }

    return ans;
}};