CountingToOne
Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom]
Cognizance - Insomnia · 2019-04-11 · by Vasyl[alphacom] · Advanced Math, Recursion
Problem Statement
Problem Statement
Consider a sequence f which satisfies,
- f(1) = 1.
- &Sigmad|n f(d) * f(n / d) = 1 for n > 1.
Constraints
- The value of N ranges from 1 to 1014 inclusive.
Examples
0)
1 Returns: 1
f(1) = 1 by definition.
1)
2 Returns: 500000004
For n = 2, f(1) * f(2)+f(2) * f(1) = 1. So f(2) = 1 / 2. (1 * 2-1) = 500000004 mod 109 + 7.
2)
4 Returns: 375000003
For n = 4, f(1) * f(4) + f(2) * f(2) + f(4) * f(1) = 1. Also we know the values of f(1) = 1 and f(2) = 1/2. So f(4) = 3 / 8. (3 * 8-1) = 375000003 mod 109 + 7.
3)
1000000000000 Returns: 224797743
4)
1401653119 Returns: 500000004
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CountingToOne with a public method int calculate(long long n) · 65 test cases · 2 s / 256 MB per case