***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;
}
Sherwin
Created at
0 likes