ta có thể thấy giữ 2 khi bình lên sẽ có khoảng cách nhất định thì các số trong khoảng đó sẽ có gtri nguyên là min của 2 số đó
vậy ta chỉ cần tìm khoảng gia trị thì sẽ tìm được giá trị cần tìm
vậy ta sẽ từ b tìm khoảng giảm dần về sau và tìm số chinh phương gần nhất với b ở mỗi lần
vậy ở ta thấy ở mỗi lần b giảm xuống /sqrt(b) mỗi lần
nên dpt tổng quat chỉnh là O(/sqrt(b))
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
#define fr(i,j,x,n) for (int i = j; i <= n; i += x)
#define frn(i,j,x,n) for (int i = j; i >= n; i -= x)
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll a,b,n;
cin >> a >> b;
ll s = 0;
while (b >= a){
ll q = sqrt(b);
n = q;
q *= q;
if (q < a) q = a;
s += n*(b - q + 1);
b = q - 1;
}
cout << s;
return 0;
}
```
Đối với bài toán này ta có thể nhận thấy được một tính chất rằng:
Căn bậc hai của mọi số trong đoạn $[l+1;r-1]$ đều bằng $\lfloor x \rfloor$, với $l,r$ là hai số chính
phương kế tiếp nhau.
Ví dụ: $l = 9$ và $r = 16$, lúc này căn bậc hai của mọi số trong đoạn $[10;15]$ đều sẽ bằng $x = 3$.
Và đối với các cặp số chính phương kề nhau tiếp theo ($l = 16$, $r = 25$, $\dots$), giá trị của $x$
sẽ tăng lên $1$.
Đến đây lời giải đã khá rõ ràng, vì số lượng số chính phương $\le 10^{12}$ chỉ có khoảng $10^6$ số
nên ta có thể thực hiện sinh toàn bộ số chính phương $\le 10^{12}$ vào một mảng và sau đó dùng
**Binary search** tìm số chính phương đầu tiên $\ge a$ và số chính phương đầu tiên $\ge b$, sau đó
ta chỉ việc tính tổng là xong.
**Code tham khảo (C++):**
```cpp
const int N = 1e6 + 5;
const ll MXN = 1e12;
vector<ll> square;
void init() {
for (ll i = 1; i * i <= MXN; ++i)
square.push_back(i * i);
}
void solve() {
ll a, b; cin >> a >> b; ll sum = 0;
int first = lower_bound(square.begin(), square.end(), a) - square.begin();
int last = lower_bound(square.begin(), square.end(), b) - square.begin();
sum += (square[first] - a) * first; sum += (b - square[last - 1] + 1) * last;
for (int i = first; i < last - 1; ++i) {
sum += (square[i + 1] - square[i]) * (i + 1);
}
cout << sum << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
init();
solve();
}
```
**Độ phức tạp:** $O(10^6)$
tien063
Created at
4 likes
menkh
Created at
1 likes