SAITAMA - Editorial

PROBLEM LINK:

Saitama and Function of Function

Setter: sayan_kashyapi

Tester: debrc , mishra_roshan

Editorialist: sayan_kashyapi

DIFFICULTY:

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
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            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
        return self.buffer.readline()
 
    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"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
        
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#input functions
def minp(): return map(int, sys.stdin.readline().rstrip().split())
def linp(): return list(map(int, sys.stdin.readline().rstrip().split()))
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.