### PROBLEM LINK:

**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.