***Bên VNOI wiki có Hàm Mobius và trong ứng dụng của hàm này mình thấy có bài gần giống với bài này nên các bạn có thể tham khảo, nhưng mình sẽ không đề cập đến nó trong Solution =D***
- Thay vì tính tổng ước của mỗi gcd(x, y) thì ta chọn 1 số a bất kì và tìm xem nó là ước của bao nhiêu số sau đó tính số cách chọn 2 số trong các số tìm được
- Với i là ước ta có __val = n/i__ số chia hết cho i (1 <= i <= n)
- Số cách chọn 2 số là: val + (val - 1) + (val - 2) + ... + 1 = __val*(val + 1)/2__
- Vì i là ước có thể tính của **mỗi** cách chọn nên tổng cách chọn i là ước: __val*(val + 1)/2*i__
- Vì các số liên tiếp có thể có cùng lượng val, VD với n = 5 và val = 1 thì 3, 4, 5 đều có val = 1
- Ta viết lại công thức: __val*(val + 1)/2 * (i + (i + 1) + (i + 2) + ... + (i + x))__ với __n/(i + x) = val__
- Giờ chỉ cần tính các val phân biệt và dùng công thức thôi
- Vì val = n/i nên để val phân biệt chỉ cần duyệt từ 1 -> sqrt(n) và val nhận 2 giá trị i và n/i
- **Có một vài số không thể có thể bị trùng, VD: 178 với i = 13 thì 178/13 = 13 (13*13 = 169) nên chỉ biến đổi để chỉ tính 1 lần**
- **Nên dùng mảng thường chứ không nên dùng vector, có thể bị tràn bộ nhớ**
- **Code mình có dùng biến vtd (vị trí đầu), vtc (vị trí cuối) của các val nên phải sort giảm dần để các i được tăng dần. (Mặc dù nếu bạn dùng tí mẹo thì không cần sort =D)**
ĐPT: O($\sqrt{n}$)
${10^7}$, code thở oxy rồi =D
**Code mẫu:**
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
const int mx = 2e7;
long long A[mx + 5];
long long x, y, n, ans = 0, de = 0;
bool kt[mx + 5] = { };
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for (long long i = 1; i*i <= n; ++i){
++de;
A[de] = i;
kt[i] = true;
}
long long m = sqrt(n);
for (long long i = m; i >= 1; --i){
long long temp = n/i;
if (temp > m || !kt[temp]){
++de;
A[de] = temp;
}
}
A[0] = -1;
long long vtd = 1;
for (int i = de; i >= 1; --i)
if (A[i] != A[i - 1]){
x = A[i];
y = A[i] + 1;
if (x%2 == 0) x /= 2;
else y /=2;
x %= mod;
y %= mod;
long long tmp1 = x*y%mod; //val*(val + 1)/2
long long vtc = n/A[i];
x = (vtc + vtd);
y = (vtc - vtd + 1);
if (x%2 == 0) x /= 2;
else y /=2;
x %= mod;
y %= mod;
long long tmp2 = x*y%mod; // (i + (i + 1) + (i + 2) + ... + (i + x))
ans = (ans + tmp1*tmp2%mod)%mod;
vtd = vtc + 1;
}
cout << ans;
}
Ta sẽ nhìn bài toán với góc nhìn khác: Với mỗi số d, đếm xem có bao nhiêu cặp (i <= j <= N) là bội của d.\
Tương tự với bài toán : https://usaco.guide/problems/cses-1082-sum-of-divisors/solution (Mời các bạn xem lời giải bài này trước).\
Công thức tính trong bài tập này sẽ là: tổng **d * C((n / d) + 1, 2)** với (1 <= d <= N).\
Trong đó C((n / d) + 1, 2) là tổ hợp chập 2 của (n / d) + 1, hay chính là số cặp (i <= j <= n) là bội của d.
```
#include <bits/stdc++.h>
using namespace std;
const int mod = int(1e9) + 7;
const int INV2 = (int(1e9) + 8) / 2;
long long range_sum(long long l, long long r) {
return (l + r) % mod * ((r - l + 1) % mod) % mod * INV2 % mod;
}
void solve() {
long long N;
cin >> N;
long long at = 1, ans = 0;
while (at <= N) {
long long x = N / at, nxt_at = N / x;
long long choose = (x % mod) * ((x + 1) % mod) % mod * INV2 % mod; //x * (x + 1) / 2
(ans += range_sum(at, nxt_at) * choose % mod) %= mod;
at = nxt_at + 1;
}
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
while(tt--) {
solve();
}
return 0;
}
```
Cách giải cho bài *Tổng Tổng Tổng*
=
Với các cặp $i = j$
-
Nó là bài [Sum of divisor](https://cses.fi/problemset/task/1082/) và đây là [lời giải](https://usaco.guide/problems/cses-1082-sum-of-divisors/solution)
**Lời giải của USACO sẽ là tiền đề cho việc giải quyết cho trường hợp còn lại**
Với các cặp $i \neq j$
-
Thay vì xét từng cặp $(i, j)$ rồi xét các ước chung. Sao ta không xét xem bao nhiêu cặp $(i, j)$ có ước chung là $g$ nào đó
Ta có công thức tính số lượng số $\in [i, n]$ chia hết cho $i$ là $\lfloor \frac{n - i}{i} \rfloor + 1$
Cho nên số lượng cặp $(i, j)$ chia hết cho $d$ là
$(\lfloor \frac{n - d}{d} \rfloor + 1)^2$
**Và từ đó, ta có công thức tính giá trị** $\sum^n_{i = 1} \sum^n_{j = 1} f(i, j)$
**chính là bằng**
$$
\sum^n_{i = 1} d * \frac{(\lfloor \frac{n - d}{d} \rfloor + 1)\lfloor \frac{n - d}{d} \rfloor}{2}
$$
Cũng tương tự như bài trên, khi chia cũng chỉ có cao tay $2\sqrt{n}$ thương khác nhau. Ta thử chia sẽ thấy ngay
Tư tưởng chính
-----------------
Thay vì tìm tổng của các ước nguyên dương của hai số $i$ và $j$.
Ta coi xem với mỗi số $d$ sẽ là ước của bao nhiêu cặp $(i, j)$ sao cho $1 \leq i \leq n$ và $1 \leq j \leq n$.
Cách làm
-----------------
### Với các cặp $(i, j)$ mà $i = j$
Với mỗi ước $d$, ta sẽ tìm số lượng cặp $(i, i)$ thỏa tính chất trên sao cho
- $1 \leq i \leq n$
- $d$ là ước của $i$
Số lượng các số $i$ thỏa tính chất trên là $\lfloor \frac{n}{d} \rfloor$.
Vậy tổng đóng góp của các cặp $(i, i)$ là:
$$\sum_{d=1}^{n} d \cdot \left\lfloor \frac{n}{d} \right\rfloor$$
Và để tối ưu độ phức tạp $O(n)$, ta sẽ dùng phép căn bậc hai để gom các giá trị bằng nhau thành một nhóm. Do ta có nhận xét:
> Số lượng phần tử có giá trị khác nhau trong dãy $\left\lfloor \frac{n}{1} \right\rfloor, \left\lfloor \frac{n}{2} \right\rfloor, \ldots, \left\lfloor \frac{n}{n} \right\rfloor$ là $2\times \sqrt{n}$.
Từ đó, ta sẽ xử lý từng nhóm một thay vì từng phần tử một.
Nếu các bạn chưa hiểu ý tưởng này, hãy tham khảo bài viết sau: [CSES - Sum of Divisors](https://usaco.guide/problems/cses-1082-sum-of-divisors/solution)
**Lưu ý:** Mong các bạn hãy hiểu ý tưởng trên trước khi đọc tiếp phần dưới
### Với các cặp $(i, j)$ mà $i \neq j$
Tương tự như trên, với mỗi ước $d$, ta sẽ tìm số lượng cặp $(i, j)$ thỏa tính chất trên sao cho
- $1 \leq i \leq j \leq n$
- $i \neq j$
Mà ta còn có
- Số lượng các số $i$ thỏa tính chất trên là $\lfloor \frac{n}{d} \rfloor$.
- Số lượng các số $j$ thỏa tính chất trên cũng là $\lfloor \frac{n}{d} \rfloor$.
- Vậy số lượng các cặp $(i, j)$ thỏa tính chất trên là $\frac{\lfloor \frac{n}{d} \rfloor \cdot \left(\lfloor \frac{n}{d} \rfloor - 1\right)}{2}$.
Vậy tổng đóng góp của các cặp $(i, j)$ với $i \neq j$ là:
$$\sum_{d=1}^{n} d \cdot \frac{\left\lfloor \frac{n}{d} \right\rfloor \cdot \left(\left\lfloor \frac{n}{d} \right\rfloor - 1\right)}{2}$$
Và tương tự như trên, ta sẽ dùng phép căn bậc hai để gom các giá trị bằng nhau thành một nhóm.
Kết luận
-----------------
Tổng đóng góp của tất cả các cặp $(i, j)$ là:
$$\sum_{d=1}^{n} d \cdot \left\lfloor \frac{n}{d} \right\rfloor + \sum_{d=1}^{n} d \cdot \frac{\left\lfloor \frac{n}{d} \right\rfloor \cdot \left(\left\lfloor \frac{n}{d} \right\rfloor - 1\right)}{2} =\sum_{d=1}^{n} d \cdot \frac{\left\lfloor \frac{n}{d} \right\rfloor \cdot \left(\left\lfloor \frac{n}{d} \right\rfloor + 1\right)}{2}$$
Và ta sẽ tính tổng trên với độ phức tạp $O(\sqrt{n})$ nhờ vào việc gom nhóm các giá trị bằng nhau.
Hoặc là các bạn có thể gom hai biểu thức này lại và chỉ tính môt lần duy nhất và tối ưu xuống còn $O(\sqrt{n})$ 😄
Sherwin
Created at
12 likes
marcus06
Created at
1 likes