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.