MAANDI - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

EASY

PREREQUISITES:

Number theory

PROBLEM:

Given an integer, find how many of its divisors contain digit 4 or 7.

QUICK EXPLANATION:

There are only O (√N) divisors of a number. Hence, we can enumerate all of them and check how many of them contain the digit 4 or 7.

EXPLANATION:

It can be observed an integer is “overlucky” iff it contains either digit 4 or 7. This is because if an integer contains digit 4 or 7, then we can remove all other digits of the number resulting in a single digit lucky number (4 or 7). On the other hand, if a number is overlucky, it certainly contains at least one lucky digit. This gives us an easy way to test if a number is overlucky: iterate through the digits of the number, if any of the digits is 4 or 7, then the number is overlucky, otherwise the number is not overlucky.

In order to find the number of overlucky divisors of a number N, we should iterate through all its divisors and count the ones which are overlucky.

Enumerating divisors:

For any divisor x of N, we can find another divisors y = N/x.
Since x * y = N, both of them cannot be greater than √N, Hence by enumerating all divisors of N smaller than √N, we can actually find all its divisors as shown below.

count := 0
for (x := 1; x * x <= N; ++x) {
  if (N mod x) continue;
  
  // x is a divisor of N.
  if (is_overlucky(x)) ++count;
  
  // Complement divisor.
  y := N/x;
  if (x != y) {
    if (is_overlucky(y)) ++count;
  }
}

This gives us an O (√N) to count the number of overlucky divisors of a number N.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution can be found here.

2 Likes
2

@jingbo_adm As I mentioned during the contest also that testcases were weak. Solutions were accepted even if you didn’t check for the redundant factors e.g. 49 Correct Answer 2 Accepted Answers 2 and 3

3

The given problem says that the range of n is 1 ≤ n ≤ 10^9. However, in my program when I use int type variables for checking the divisors x and N/x for overlucky number, I am given WA. Changing N to long int gave me AC. Why is that? (I kept the variable for keeping the count of overlucky number as long int beforehand).