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")

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)

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()

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)

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()

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))