A. Love Triangle
One way to verify a function is by checking if there exists an "i" for which the output of the function, when applied three times consecutively (i.e., f(f(f(i)))), is equal to "i". In other words, the condition to check is whether f(f(f(i))) equals "i"
length = int(input())
planes = list(map(lambda x: int(x) - 1, input().split()))
flag = False
for i in range(length):
if planes[planes[planes[i]]] == i:
flag = True
print("YES" if flag else "NO")
B. Divide and Multiply
To maximize the sum of an array, we can first divide all numbers in the array by 2 as many times as possible and count the number of successful divisions as "k". Then, we should identify the largest number remaining in the array after these divisions. To obtain the maximum sum, we need to multiply this largest remaining number by 2 raised to the power of "k".
numOfTests = int(input())
for _ in range(numOfTests):
length = int(input())
arr = list(map(int, input().split()))
twos = 0
for i in range(length):
while arr[i] % 2 == 0:
twos += 1
arr[i] //= 2
arr.sort()
total = sum(arr[:-1]) + (arr[-1] * (1 << twos))
print(total)
C. Sherlock and his girlfriend
We have a bunch of jewelry pieces with different prices. We want to color them in a way that if the price of any piece is a multiple of a prime number, then it should have a different color than the other pieces whose prices are also multiples of that prime number.
To solve this, we need to first find all the prime numbers up to a certain range (in this case, up to number of jewelries + 1) using the Sieve of Eratosthenes method. Then, we can color all the jewelry pieces whose prices are prime numbers with one color, and color the rest of the pieces with a different color. This ensures that if a piece's price is a multiple of a prime number, it will have a different color than the other pieces whose prices are also multiples of that prime number.
def build_sieve(num_jewelries):
sieve = [1 for i in range(num_jewelries)]
sieve[1] = 1
i = 2
while i * i <= num_jewelries:
if sieve[i] == 1:
for j in range(i * i, num_jewelries, i):
sieve[j] = 2
i += 1
return sieve
def main():
num_jewelries = int(input())
sieve = build_sieve(num_jewelries + 2)
if num_jewelries > 2:
print(2)
else:
print(1)
for i in range(2, num_jewelries + 2):
print(sieve[i], end = " ")
main()
D. Fadi and LCM
Given a number num, we want to find two positive integers a and b such that their LCM is equal to num and the maximum of a and b is minimized. To do so, we can start by finding the prime factors of num. We can then divide the prime factors into two sets a and b such that their product is num.
To minimize the maximum of a and b, we want to divide the prime factors as evenly as possible between a and b. This means that we want to split the prime factors into two sets of approximately equal size. To do so, we can start by initializing a to 1 and b to num, and then iterate over all the possible factors of num starting from 2.
For each factor i, we check if it is a divisor of num and whether the LCM of i and num // i is equal to num. If both conditions are satisfied, we update a and b accordingly. By doing so, we are effectively finding a pair of positive integers a and b such that their product is num and their greatest common divisor (GCD) is 1, i.e., they are coprime.
import math
num = int(input())
a = 1
b = num
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0 and math.lcm(i, num // i) == num:
a = i
b = num // i
print(a, b)
E. Modified GCD
To solve this problem, we need to find the greatest common divisor (GCD) of the given integers a and b that lies in a range specified by the query. We can use the fact that any divisor of a and b must also be a divisor of their GCD.
After computing the GCD of a and b, we can obtain all its factors by iterating from 1 to the square root of GCD, and checking if it divides the GCD without a remainder. Once we have the factors of the GCD, we can check if they fall within the range of the current query.
If there are factors within the range, we can pick the maximum factor that satisfies the conditions. Otherwise, we output -1 for the current query, indicating that there is no common divisor within the range.
def gcd(num1, num2):
while num2:
num1 %= num2
num1, num2 = num2, num1
return num1
def find_factors(num):
factors = []
d = 1
while d * d <= num:
if num % d == 0:
factors.append(d)
factors.append(num // d)
d += 1
if num > 1:
factors.append(num)
return sorted(factors)
def main():
num1, num2 = map(int, input().split())
num_queries = int(input())
cur_gcd = gcd(num1, num2)
factors = find_factors(cur_gcd)
for query in range(num_queries):
low, high = map(int, input().split())
modified_gcd = -1
for factor in factors:
if low <= factor <= high:
modified_gcd = factor
print(modified_gcd)
main()
F. Power Products
We need to count the number of pairs of integers ai and aj such that there exists an integer x where ai * aj = x^k.
For each number ai, we can find its prime factorization. Let's say it is ai = p1^x1 * p2^x2 * ... * pn^xn.
To make ai * aj = x^k, we need to choose aj such that its prime factorization only includes the same prime factors as ai, but with exponents that are multiples of k.
For each prime factor pi in ai, let's calculate the remainder of xi when divided by k. If the remainder is 0, then we don't need to change the exponent of pi. But if the remainder is r > 0, then we need to change the exponent of pi to (k — r).
Let's call the resulting product of adjusted prime factors for ai, the "multiplier" of ai.
Now, we can keep track of the number of times we've seen each multiplier by using a dictionary (in Python, we can use a defaultdict). For each ai, we can multiply its prime factors with adjusted exponents to get its multiplier, and add to the answer the number of times we've seen the same multiplier before.
Finally, we can update the dictionary by incrementing the count of the multiplier we've seen for this ai.
At the end, the answer will be the number of pairs that we have counted.
from collections import defaultdict
def prime_factorization(num):
factors = defaultdict(int)
d = 2
while d * d <= num:
while (num % d == 0):
factors[d] += 1
num //= d
d += 1
if num > 1:
factors[num] += 1
return factors
def main():
length, power = map(int, input().split())
nums = list(map(int, input().split()))
multiplicand = defaultdict(int)
ans = 0
for num in nums:
prime_factors = prime_factorization(num)
multiplier = 1
for factor in prime_factors:
exponent = prime_factors[factor]
modulo = exponent % power
if modulo != 0:
multiplier *= (factor ** (power - modulo))
ans += multiplicand[multiplier]
cur_multiplicand = 1
for factor in prime_factors:
exponent = prime_factors[factor]
modulo = exponent % power
cur_multiplicand *= (factor ** modulo)
multiplicand[cur_multiplicand] += 1
print(ans)
main()
Time Complexity: O(n.sqrt(n))
from collections import defaultdict
def build_sieve(num):
sieve = [0 for i in range(num + 1)]
for i in range(num + 1):
sieve[i] = i
i = 2
while i * i <= num:
if sieve[i] == i:
for j in range(i * i, num + 1, i):
if (sieve[j] == j):
sieve[j] = i
i += 1
return sieve
def prime_factorization(num, sieve):
factors = defaultdict(int)
d = 2
while num > 1:
sf = sieve[num]
factors[sf] += 1
num //= sf
return factors
def main():
length, power = map(int, input().split())
nums = list(map(int, input().split()))
multiplicand = defaultdict(int)
sieve = build_sieve(100_000)
ans = 0
for num in nums:
prime_factors = prime_factorization(num, sieve)
multiplier = 1
for factor in prime_factors:
exponent = prime_factors[factor]
modulo = exponent % power
if modulo != 0:
multiplier *= (factor ** (power - modulo))
ans += multiplicand[multiplier]
cur_multiplicand = 1
for factor in prime_factors:
exponent = prime_factors[factor]
modulo = exponent % power
cur_multiplicand *= (factor ** modulo)
multiplicand[cur_multiplicand] += 1
print(ans)
main()
Time Complexity: O(n*log(n))