***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;
}
```
Sherwin
Created at
8 likes
marcus06
Created at
1 likes