CLPRI - Editorial

PROBLEM LINK: Clever Priest

Author: Rituj Aryan
Tester: Rohit Doshi






Given a binary string of length N with all bits 0, apply N operations on it (in any order).

In any operation, choose an integer K (1 \leq K \leq N) and flip all bits present at i_{th} position (1-based indexing) such that i \bmod K = 0. (K should be unique in all operations)

Determine the number of set bits in the final string after all N operations.


Does order of operations actually matter?


Observe that no matter in which order you apply N operations, answer will always be the same.

Notice that a bit at position i will be flipped for all K such that i \bmod K = 0.
So, that means if i has even number of factors, it will be flipped even times which means it will always be 0 but for odd factors it will become 1.

So, we need to count all numbers X (1 \leq X \leq N) such that X has odd factors.
A number has odd factors only when it is a perfect square.

Therefore, answer is number of perfect squares less than N which is equal to \lfloor \sqrt N \rfloor

NOTE: The floor function (\lfloor X \rfloor) takes as input a real number X, and gives as output the greatest integer \leq X


Setter's Solution (CPP)
using namespace std;
#define ll long long
int t=1;
int main()
	while(t--) {
		ll n,ans;
Tester's Solution (Python)
from math import sqrt

def solve(n):
	return int(sqrt(n))

t = int(input())
for _ in range(t):
	n = int(input())
	ans = solve(n)

Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome :smile: