HolyNumbers
SRM 552 · 2012-06-05 · by Egor
Problem Statement
NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.
In John's country, the main religion is based on holy numbers. The religion claims something silly like "the holy numbers are those that contain only 4s and 7s in their decimal expansion".
John is a heretic. He does believe in holy numbers, but he is convinced that the religion is mistaken in their definition. The holiness of a number simply cannot depend on the base in which it is represented! After a long meditation, John realized that the prime factorization of a number does not depend on the base in which the number is represented. That was the correct way!
Many years later, John's theory was finally ready. A prime p likes the number x if one of the following two conditions is satisfied:
- The prime p does not divide x.
- The prime p does divide x, p is less than or equal to maximalPrime, and the highest power of p that divides x is odd. (In other words, there is a positive odd integer k such that pk divides x, and pk+1 does not divide x.)
The number x is considered holy if all primes like it.
You are given a
Notes
- A prime number is a positive integer with exactly 2 positive integer divisors. The first few primes are 2, 3, 5, 7, 11, ...
Constraints
- upTo is between 1 and 1010, inclusive.
- maximalPrime is between 1 and 106, inclusive.
10 100 Returns: 8
1, 2, 3, 5, 6, 7, 8 and 10 are holy numbers.
10 3 Returns: 5
5, 7 and 10 are no longer holy.
10000000000 1000000 Returns: 3336332555
1 1 Returns: 1
2 2 Returns: 2
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class HolyNumbers with a public method long long count(long long upTo, int maximalPrime) · 76 test cases · 2 s / 256 MB per case