JOIN
Get Time

   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