Kaosar və EM ( > w < ) (Həll təhlili)

Həll

Hər hansı bir tam ədəd $x$ üçün k=\lfloor x \rfloor olaraq təyin edin.

Sonra hər bir tam ədəd $x$ dəqiq bir intervallarda yerləşir: x \in [k^2,(k+1)^2-1].

Bu tam blok daxilində, \lfloor \sqrt{x} \rfloor = k.

Verilən şərt x \equiv \lfloor \sqrt{x} \rfloor ( mod $p$ )

$k$-nın tərifini istifadə edərək, bu x \equiv k (mod $p$) olur.

Beləliklə, hər bir $k$ dəyəri üçün, [k^2,(k+1)^2-1]\cap [l,r] aralığında tam ədədləri saymalıyıq

belə ki x\equiv k ( mod $p$ )

İndi,

Xüsusi bir hal p=1-dir

onda hər bir tam ədəd şərti ödəyir. Buna görə cavab = r-l+1.

Başqa halda əvvəlcə $k$-nın aralığını müəyyən edin, k_{\min}=\lfloor \sqrt{l} \rfloor və k_{\max}=\lfloor \sqrt{r} \rfloor hesablayın.

İndi k_{\min}-dən k_{\max}-a qədər hər bir tam ədəd $k$ üçün:

[l, r] daxilində etibarlı intervalları təyin edin: L=max(l,k^2) və R=min(r,(s+1)^2-1)

Əgər L>R-dirsə, bu $k$ dəyərini keçin.

İndi $[L,R]$ aralığında $x$-ləri sayın ki, x \equiv s (mod $p$) şərtini ödəsin.

Belə bir ən kiçik tam ədəd f=L+((s−L)\mod p+p)\mod p.

Əgər f>R-dirsə, bu blok üçün say $0$-dır.

Başqa halda blokdakı etibarlı tam ədədlərin sayı

Cavab $\sum v$-dir.

Çətinlik:

$s$ dəyərlərinin sayı ən çox \lfloor \sqrt{r} \rfloor-dir, çünki r\le 10^9

\sqrt{r}\le 31623. Beləliklə, hər test halı üçün vaxt çətinliyi O(\sqrt{r})-dir.

bu t \le 1000 üçün səmərəlidir.

#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;
}