# SAITAMA - Editorial

Saitama and Function of Function

Setter: sayan_kashyapi

Tester: debrc , mishra_roshan

Editorialist: sayan_kashyapi

Simple

# PREREQUISITES:

Number Theoretic Functions, Euler’s Totient Function \phi(n).

# PROBLEM:

You are given a function y(x) = x^2 - x and another function f() which is basically the Euler’s Totient function. You have to calculate the value of f(y(x)) i.e. the no. of relative prime to y(x) from 1 to y(x).

# EXPLANATION

Euler’s totient function, also known as phi-function \phi(n), counts the number of integers between 1 and n inclusive, which are coprime to n. Two numbers are coprime if their greatest common divisor equals 1 (1 is considered to be coprime to any number).

For better understanding see the implementation using factorization.

# TIME COMPLEXITY

Time complexity is O(\sqrt{N}) for each test case.

# SOLUTIONS:

Setter's Solution
C++
#include <bits/stdc++.h>
using namespace std;
int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
int main()
{
int t;
cin>>t;
while(t--){
int x;
cin>>x;
cout << phi(x * x - x) << "\n";
}
return 0;
}

Tester's Solution
Java
import java.util.*;
public class Main {
static int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
}
if (n > 1)
result -= result / n;
return result;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();

while(t-->0){
int x=sc.nextInt();
System.out.println(phi(x * x - x));
}
}
}

Python
# cook your dish here
#import modules here
import math,sys,os
#from itertools import permutations, combinations
# from collections import defaultdict,deque,OrderedDict,Counter
# import bisect as bi
#import heapq
from io import BytesIO, IOBase
mod=10**9+7

# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

while True:
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0

while self.newlines == 0:
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

#input functions
def inp(): return int(input())
def print_list(l):
print(' '.join(map(str,l)))
def yes():
print("YES")
def no():
print("NO")

# functions
# def BinarySearch(a,x):
#     i=bi.bisect_left(a, x)
#     if i != len(a) and a[i] == x:
#         return i
#     else:
#         return -1

# def gcd(a,b):
#     return math.gcd(a,b)

# def is_prime(n):
#     """returns True if n is prime else False"""
#     if n < 5 or n & 1 == 0 or n % 3 == 0:
#         return 2 <= n <= 3
#     s = ((n - 1) & (1 - n)).bit_length() - 1
#     d = n >> s
#     for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
#         p = pow(a, d, n)
#         if p == 1 or p == n - 1 or a % n == 0:
#             continue
#         for _ in range(s):
#             p = (p * p) % n
#             if p == n - 1:
#                 break
#         else:
#             return False
#     return True

# def mulinverse(a):
#     return pow(a,mod-2,mod)

####################Let's Go Baby########################
def phi(n):
result = n;
p = 2;
while(p * p <= n):
if (n % p == 0):
while (n % p == 0):
n = int(n / p);
result -= int(result / p);
p += 1;
if (n > 1):
result -= int(result / n);
return result;

for _ in range(inp()):
x=inp()
print(phi(x*x-x))


Feel free to Share your approach.
Suggestions are welcomed as always had been.