Connection Status:
Competition Arena > SmoothDivisors

SmoothDivisors

SRM 811 · 2021-08-19 · by misof

SRM 811 · 2021-08-19 · by misof · Math
Class Name: SmoothDivisors
Return Type: int
Method Name: count
Arg Types: (int, int)
Problem Statement

Problem Statement

This problem has a time limit of 4 seconds. The memory limit is standard: 256 MB.


A set of integers is called smooth if it can be arranged into a cyclic sequence such that no pair of adjacent elements is coprime. (See Notes for a definition of "coprime".)

(An empty sequence has no pairs of adjacent elements. In a one-element sequence the only element is considered to be its own neighbor and therefore there is one pair of adjacent elements.)


Examples:

  • The set {1, 2, 3, 4, 5} is not smooth because in any cyclic sequence the number 1 has to have two neighbors and it will be coprime with each of them, regardless of what they are.
  • The set {2, 4, 6, 8, 10} is smooth: in fact, any cyclic sequence of these elements works as each two of them have a common factor that is at least 2.
  • The set {2, 4, 27, 54, 666} is smooth: e.g., the cyclic sequence 4, 2, 666, 27, 54 has the desired property.
  • The set {2, 5, 10000} is not smooth. In particular, the sequence 2, 10000, 5 does not work - remember that the sequence is cyclic and therefore 2 and 5 must also have a common factor that is greater than 1.
  • The empty set is smooth, with the empty sequence as a witness.
  • The set {1} is not smooth.
  • The set {42} is smooth.

Proper divisors of a positive integer X are positive integers that divide X and lie strictly between 1 and X itself. For example, 1 and 47 each have no proper divisors, and 14 has two proper divisors: 2 and 7.

A number is called smooth if the set of its proper divisors is smooth.


You are given two integers A and B. Count all smooth integers in the closed range [A, B].

Notes

  • Positive integers X and Y are called coprime if their greatest common divisor is 1.

Constraints

  • 1 <= A <= B <= 40,000,000.
Examples
0)
213
219
Returns: 1

The only smooth number in this range is 216.

1)
47
49
Returns: 3

All three numbers in this range are smooth. The set of proper divisors of 47 is {}, the set of proper divisors of 48 is { 2, 3, 4, 6, 8, 12, 16, 24 }, and the set of proper divisors of 49 is { 7 }.

2)
1
40000000
Returns: 31501134
3)
1
5
Returns: 5

Again, all five numbers in this range are smooth.

4)
34000046
34000046
Returns: 0

This number is not smooth.

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

Coding Area

Language: C++17 · define a public class SmoothDivisors with a public method int count(int A, int B) · 60 test cases · 2 s / 256 MB per case

Submitting as anonymous