Number Theory and Binary Search

Description

• Topics : Number Theory, Binary Search
• Link to the contest

Editorial

caution

Don’t read the editorial, if you have not attempted or read the problems. It would hamper your thinking capability, if you do so.

A. Find $x^{F(n)}$ mod m

• Problem
• Editorial
• Code

Given 3 positive integers - $x$, $n$ and $m$. Find value of $x^{F(n)}$ mod $m$ .
The function $F(n)$ is defined as the product of square of primes up to $n$ (inclusive).
For eg. $F(5) = 2^2 \cdot 3^2 \cdot 5^2 = 900$ .

Constraints

• $1 \leq x,m \leq 10^9$
• $2 \leq n \leq 10^6$

B. Simple Maths

• Problem
• Editorial
• Code

You will be given 5 number $n$ ,$m$ , $a$ , $b$ , $c$ . You will make 3 more numbers $A$ , $B$ , $C$ from it.

$A = a \cdot m$
$B = A \cdot (b + c)$
$C = 5 \cdot B + A \cdot (floor(\log_{10}{(b \cdot c)}))$

You task is to computer $f(n)$ % $m$ where
$f(i) = (A \cdot i^9 + i^i \cdot (B \cdot i!+1) + C \cdot i^{i^i}) \cdot f(i-1)$

Note : $f(0) = 1$

Constraints

• $1 \leq n \leq 10^{18}$
• $1 \leq m \leq 10^6$
• $1 \leq a,b,c \leq 10^{12}$

C. Candy Distribution

• Problem
• Editorial
• Code

In the Town of Candyland, there are $K$ candy vendors who need to distribute candies to the kids of the town. Candyland can be represented as the x-axis where kids are standing at different $x$ coordinates, which are given to you. A vendor can only serve kids which are in his range, for example, if a vendor is placed at $X$ and his range is $E$ then all kids in the range $[X-E,X+E]$ can get candies from him. All the vendors have an equal range $E$.

Since the vendors are lazy so they want you to find the minimum range $E$ such that all the kids in Candyland can get candies.

Constraints

• $1 \leq n,k \leq 10^4$
• $10^{-9} \leq X_i \leq 10^{9}$

D. Seems to be easy xD

• Problem
• Editorial
• Code

Given an array $A$ (having the values of all elements in range [0,2000] ) of length $N$.
Each index $i ∈ [1,N]$ has an initial weight of $W_i$ units. You have to perform $Q$ queries. The queries can be of 2 types:

Type $1$: $1$ $X$
Type $2$: $2$ $V$ $L$ $R$

Type $1$ queries ask you to increase the weight of all indices by $X$ units.

Type $2$ queries ask you to calculate the total weight contributed by elements having value $V$ in the index range $[L,R]$

Constraints

• $1 \leq N,Q \leq 5 \cdot 10^5$
• $1 \leq A_i,V \leq 2000$
• $0 \leq W_i, X \leq 100$
• $1 \leq L \leq R \leq N$

E. Rahul and his set

• Problem
• Editorial
• Code

Rahul has a set $S$ consisting of the first $N$ natural numbers.

He thinks that 'wellness' of a subset $M$ ⊆ $S$ is equal to the maximum of $gcd(a,b)$ over all pairs $(a,b)$ such that both $a$ and $b$ are in $M$ and $a \neq b$.

Rahul is an organized guy and for each $k$ ∈ {$2,3,…,N$} he wants to find a subset that has the smallest wellness among all subsets in $S$ of size $k$. There can be more than one subset with the smallest wellness and the same size, but you don't need to worry about it. Rahul wants to find all the subsets himself, but he needs your help to find the smallest possible wellness for each size $k$, will name it $I_k$.

Please, help Rahul to find $I_2, I_3, ..., I_n$.

Constraints

• $2 \leq N \leq 5 \cdot 10^5$