Connection Status:
Competition Arena > AlwaysDefined

AlwaysDefined

TCO14 Round 2B · 2014-03-26 · by ivan_metelsky

TCO14 Round 2B · 2014-03-26 · by ivan_metelsky · Search, Simple Math
Class Name: AlwaysDefined
Return Type: long
Method Name: countIntegers
Arg Types: (long long, long long, int)
Problem Statement

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.

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
4)
1
1
2
Returns: 1

Submissions are judged against all 245 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AlwaysDefined with a public method long long countIntegers(long long L, long long R, int W) · 245 test cases · 2 s / 256 MB per case

Submitting as anonymous