Kaosar and EM ( > w < ) (Editorial)

Solution

For any integer $x$, define k=\lfloor x \rfloor.

Then every integer $x$ lies in exactly one interval: x \in [k^2,(k+1)^2-1].

Inside this entire block, \lfloor \sqrt{x} \rfloor = k.

The condition given is x \equiv \lfloor \sqrt{x} \rfloor ( mod $p$ )

Using the definition of $k$, this becomes x \equiv k (mod $p$).

So for each value of $k$, we need to count integers x \in [k^2,(k+1)^2-1]\cap [l,r]

such that x\equiv k ( mod $p$ )

Now,

A special case is p=1

then every integer satisfies the condition. Therefore answer = r-l+1.

Otherwise first determine the range of $k$, compute k_{\min}=\lfloor \sqrt{l} \rfloor and k_{\max}=\lfloor \sqrt{r} \rfloor

Now for each integer $k$ from k_{\min} to k_{\max}:

Define the valid interval inside [l, r]: L=max(l,k^2) and R=min(r,(s+1)^2-1)

If L>R then skip this value of $k$.

Now count integers $x$ in $[L,R]$ satisfying x \equiv s (mod $p$).

The smallest such integer is f=L+((s−L)\mod p+p)\mod p.

If f>R then the count for this block is $0$.

Otherwise the valid number of integers in the block is

The answer is $\sum v$.

Complexity:

The number of values of $s$ is at most \lfloor \sqrt{r} \rfloor since r\le 10^9

\sqrt{r}\le 31623. Thus the time complexity per test case is O(\sqrt{r}).

which is efficient for t \le 1000.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
    ll l, r; int p;
    cin>>l>>r>>p;
    ll ans = 0;
    for (ll k =0; k*k<=r;++k) {
        ll lo =max(l, k * k);
        ll hi =min(r, k * k + 2 * k);
        if (lo> hi) continue;
        ll del=((k - lo) % p + p) % p;
        ll x=lo + del;
        if (x>hi) continue;
        ans += (hi-x)/p+1;
    }
    cout << ans << endl;
    }
    return 0;
}