JOIN

 Problem Statement

Problem Statement for AlwaysDefined

### 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

0)

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

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

 `1282` `1410` `10`
`Returns: 42`
3)

 `29195807` `273209804877` `42`
`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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
2014 TCO Algorithm Round 2B - Division I, Level Three
2014 TCO Algorithm Parallel Round 2B - Division I, Level Three