Number theory codeforces

#1

https://codeforces.com/contest/1485/problem/C

Sir I am not understanding this editorial can you explain this ?

#2 
We can notice that, if ⌊ab⌋=a mod b=k⌊ab⌋=a mod b=k, then aa can be written as kb+kkb+k (b>kb>k). Since b>kb>k, we have that k2<kb+k=a≤xk2<kb+k=a≤x. Hence k≤x−−√k≤x.

Now let's count special pairs for any fixed kk (1≤k≤x−−√1≤k≤x). For each kk, you have to count the number of bb such that b>kb>k, 1≤b≤y1≤b≤y, 1≤kb+k≤x1≤kb+k≤x. The second condition is equivalent to 1≤b≤x/k−11≤b≤x/k−1.

Therefore, for any fixed k>0k>0, the number of special pairs (a≤xa≤x; b≤yb≤y) is max(0,min(y,x/k−1)−k)max(0,min(y,x/k−1)−k). The result is the sum of the number of special pairs for each kk.

Complexity: O(x−−√)O(x).

now in this editorial what is your doubt?

have to learn number therory ?

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.