AlwaysDefined | Topcoder Archive

Problem Statement

Given is a positive integer W. We will use W to define a function f. The value f(x) is computed as follows:

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).

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.)

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.

Definition

Class:: AlwaysDefined
Method:: countIntegers
Parameters:: long, long, int
Returns:: long
Method signature:: long countIntegers(long L, long R, int W)
(be sure your method is public)

Constraints

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.

Examples

```
10
```
```
10
```
```
4
```
```
Returns: 1
```
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.
```
1
```
```
99
```
```
2
```
```
Returns: 50
```
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.
```
1282
```
```
1410
```
```
10
```
```
Returns: 42
```

29195807

273209804877

Returns: 31415926535

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)2024, Topcoder, Inc. All rights reserved.