This page is still under construction.

Parts of this page are still being built. What you see may change.

Coprime

Time limit1sMemory limit512 MB

Summary

Given n and k up to 1e14, sum all integers in [1, nk] that are coprime with n, using inclusion-exclusion over n's prime factors and periodicity mod n.

Level: Medium7 of 10
Topics: Number theory, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

You are given two integers $n$ and $k$ . Find the sum of all positive integers less than or equal to $nk$ and coprime with $n$ .

Input

The first and only line of the input contains two integers $n$ and $k$ .

Output

Print the answer.

Constraints

$1 \le n, \, k \le 10^{14}$
All values in input are integers.

Examples1

Example 1
Input
```
2 5
```
Expected output
```
25
```

Loading...