ProperDivisors
SRM 394 · 2008-03-22 · by Xixas
SRM 394 · 2008-03-22 · by Xixas · Math, Simple Search, Iteration
Problem Statement
Problem Statement
An integer k greater than 0 is called a cool divisor of m if it is less than m and divides m, but k^n does not divide m. Let d(m) denote the number of cool divisors that exist for an integer m. Given two integers a and b return the sum d(a) + d(a + 1) + ... + d(a + b).
Notes
- The result will always fit into a signed 32-bit integer.
Constraints
- a will be between 1 and 1000000 (10^6), inclusive.
- b will be between 1 and 10000000 (10^7), inclusive.
- n will be between 2 and 10, inclusive.
Examples
0)
32 1 3 Returns: 5
The cool divisors of 32 are 4, 8 and 16 so d(32) = 3; the cool divisors of 33 are 3 and 11 so d(33) = 2. Hence the desired sum d(32) + d(33) = 3 + 2 = 5.
1)
1 12 2 Returns: 8
2)
1000000 10000000 10 Returns: 146066338
3)
1000000 10000000 5 Returns: 145707011
4)
1 1 10 Returns: 0
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ProperDivisors with a public method int analyzeInterval(int a, int b, int n) · 92 test cases · 2 s / 256 MB per case