| ||Given is a positive integer W.
We will use W to define a function f.
The value f(x) is computed as follows:
For any positive integer x, consider the following infinite sequence:
x, f(x), f(f(x)), f(f(f(x))), and so on.
We say that f is always defined for x if all the terms of the above sequence are defined.
(In other words, there is no positive integer k such that f^k(x) is undefined.
Here, f^k denotes f applied k times.)
- If x is not a positive integer, f(x) is undefined.
- Let y = x modulo W. If y is zero, f(x) is undefined.
- Otherwise, f(x) = x/y (where "/" denotes exact real division).
You are given longs L and R, and the int W used in our function f.
Count all x between L and R, inclusive, such that f is always defined for x.
Return that count.
|Parameters:||long, long, int|
|Method signature:||long countIntegers(long L, long R, int W)|
|(be sure your method is public)|
|-||L will be between 1 and 10^18, inclusive.|
|-||R will be between L and 10^18, inclusive.|
|-||W will be between 2 and 3000, inclusive.|
|For W = 4, we have f(10) = 5, f(f(10)) = 5, f(f(f(10))) = 5 and so on, thus f is always defined for x = 10.|
|For W = 2, f is always defined for odd integers but not for even integers. There are 50 odd integers between 1 and 99, inclusive.|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.