SRM 523 DIV1 Easy - CountingSeries (復習××)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10957&rd=14548

1からupperBoundまでの数が与えられる。
また、a,b,c,dの正の整数が与えられる。
このとき、a+b*x または c*d^y(x,yは任意の整数)を満たす数がいくつあるか求める。

解き方


「a+b*x」、「c*d^y」は重複する場合があるので、
重複した場合は1度しか計算しない処理が必要。

「a+b*x」では、各整数は10^12のため全探索では不可。
upperBoundがa以上であれば、 (upperBound-a)/b +1が満たす全ての数になる。

「c*d^y」は全探索が可能。
各数に対して「a+b*x」でも表わせないか判定し重複を調べる。
(同じようにa以上かどうかを調べる)
ただしd=1のときは無限ループになるのでbreak処理が必要。

Challengeポイント
階乗が出てくる場合は1の階乗のbreak処理が入っているか?
数の判定の際は正負の判定が入っているか?

コード



class CountingSeries {

public: long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
long long ans=upperBound>=a ? (upperBound-a)/b+1 :0;

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

return ans;
}

};
このエントリーをはてなブックマークに追加