FunctionGame | Topcoder Archive

Problem Statement

You are given the ints m and n. Consider the following expression:

Above, F is Euler's totient function. That is, F(n) is the number of positive integers that are <= n and relatively prime to n.

Let X be the value of the above expression. Since the value can be very large, compute and return the value (X modulo 1,000,000,007).

Definition

Class:: FunctionGame
Method:: findValue
Parameters:: int, int
Returns:: int
Method signature:: int findValue(int m, int n)
(be sure your method is public)

Notes

You can read more about Euler's totient function here: http://mathworld.wolfram.com/TotientFunction.html
Note that F(1) = 1.

Constraints

m will be between 1 and 10^6, inclusive.
n will be between 1 and 10^9, inclusive.

Examples

```
1
```
```
3
```
```
Returns: 3
```
The sum is F(1^1) + F(1^2) + F(1^3) = 1 + 1 + 1 = 3.
```
3
```
```
1
```
```
Returns: 4
```
This time the sum is F(1^1) + F(2^1) + F(3^1) = 1 + 1 + 2 = 4.
```
3
```
```
2
```
```
Returns: 13
```
This sum is F(1^1) + F(1^2) + F(2^1) + F(2^2) + F(3^1) + F(3^2).

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.