CountingToOne | Topcoder Archive

Problem Statement

Consider a sequence f which satisfies,

f(1) = 1.
&Sigma_d|n f(d) * f(n / d) = 1 for n > 1.

Your task is to calculate f(N). If your answer is of the from p / q, return (p * q^-1) mod (10⁹ + 7).

Definition

Class:: CountingToOne
Method:: calculate
Parameters:: long
Returns:: int
Method signature:: int calculate(long n)
(be sure your method is public)

Constraints

The value of N ranges from 1 to 1014 inclusive.

Examples

```
1
```
```
Returns: 1
```
f(1) = 1 by definition.
```
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.
```
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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.