Euler function


Plus
Pin


Problem description Progress
ID 31849. Irreducible fractions
Темы: Arithmetic Algorithms    Euler function   

A fraction \({m \over n}\) is called a proper irreducible fraction if \(0 < m < ; n\) and \(gcd (m, n) = 1\). Find the number of proper irreducible fractions with denominator n.
 
Input data 
The first line specifies the number of denominators for which to find the number of proper irreducible fractions N (\(N <=100\)). Each subsequent line is a number n (\(n < 10^9\)). 
 
Imprint 
For each n print the answer to the problem in a separate line.
 

 

Examples
# Input Output
1
4
23
23456
7
17
 
 22
11712
6
16

ID 33687. Euler function
Темы: Euler function   

Given a natural number \(n  <= 10^9,\) determine the number of natural numbers less than \(n\ ) and coprime to \(n\). This number is denoted by \( f(n) \) and is called Euler's phi function. The complexity of the algorithm should be \( O(\sqrt{n})\) .

Input
The input is a natural number n.

Imprint
Print the answer to the problem.
 

 

Examples
# Input Output
1 2 1

ID 31850. Euler function sum
Темы: Euler function   

Calculate the sum of Euler functions of the form: \(\phi(1) + \phi(p) + \phi(p^2) + ... + \phi(p^\ alpha)\),  where  \(p\)  - prime number, \(\alpha\)-  natural number.

Input
Two space-separated numbers are given in one line \(p\) and \( \alpha\)  (\(p <=11, \alpha <=60 \)).

Imprint 
Print the answer to the problem.
 

 

Example
# Input Output
1 2 2 4