Tác giả:
Reviewer:
Hàm số Euler hay phi hàm Euler của một số nguyên dương là số lượng số bé hơn hoặc bằng và nguyên tố cùng nhau với . Kí hiệu của hàm số Euler là (hoặc ).
Từ định nghĩa, ta có thể tính được và với là một số nguyên tố.
Đối với , ta dễ dàng thấy được rằng với các số từ đến : với là hàm ước chung lớn nhất của hai số nguyên.
Đối với , ta thấy các số thoả mãn chỉ có thể là các bội số của , tức là các số thuộc tập hợp . Vì trong số từ đến có số là bội số của nên ta có số nguyên tố cùng nhau với .
Nếu như ta đã biết trước giá trị phi hàm Euler của hai số và , ta có thể tính được giá trị .
Từ các công thức trên, ta có thể tính giá trị phi hàm Euler của các số với là các số nguyên tố, là luỹ thừa tương ứng:
Ví dụ, .
Để đưa công thức trên vào chương trình, ta đơn giản hoá công thức để tăng tốc thuật toán. Ta có:
Từ đây, ta có công thức tính bằng:
Với là các ước nguyên tố của .
int phi(int n){
int totient = n;
for(int i = 2; 1ll * i * i <= n; ++i){
if(n % i == 0){ // i là số nguyên tố
while(n % i == 0) n /= i;
totient -= totient / i; // tương đương totient * (1 - 1/i)
}
}
if(n != 1) totient -= totient / n;
return totient;
}
Độ phức tạp của thuật toán bằng .
Ta có thể chỉnh sửa thuật toán sàng số nguyên tố để tính giá trị phi hàm Euler của các số từ đến .
int phi[N];
void sievePhi(int n){
for(int i = 1; i <= n; ++i) phi[i] = i;
for(int i = 2; i <= n; ++i){
if(phi[i] == i){ // i là số nguyên tố
for(int j = i; j <= n; j += i){
phi[j] -= phi[j] / i; // tương đương phi[j] * (1 - 1/i)
}
}
}
}
Vì phi hàm Euler là một hàm nhân tính, ta có thể tính giá trị phi hàm Euler dựa trên công thức
Với là các ước của nhỏ hơn .
int phi[N];
void sievePhi(int n){
for(int i = 1; i <= n; ++i) phi[i] = i;
for(int i = 1; i <= n; ++i){
for(int j = i + i; j <= n; j += i){
phi[j] -= phi[i];
}
}
}
Phi hàm Euler xuất hiện trong định lí Euler: với hai số và nguyên tố cùng nhau, ta có:
Từ đây, ta dễ dàng tính được giá trị nghịch đảo modulo của bằng .
Với hai số và nguyên tố cùng nhau, nếu , thì:
Tính chất này rất hữu dụng khi ta muốn tính luỹ thừa bậc của với số mũ rất lớn:
Tóm tắt đề: cho hai số và (), tính:
với là bội số thứ của .
Dễ thấy, việc tính các trước và tính giá trị phi hàm Euler của nó sẽ không hiệu quả, khi có tới tận bội số và giá trị các bội số có thể lên tới .
Thay vì thế, ta có thể tính trước giá trị phi hàm Euler của các từ đến và giá trị , sau đó áp dụng công thức tính phi hàm Euler của tích hai số để giải quyết bài toán.
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;
const int MOD = 998'244'353;
int phi[N];
int calcPhi(int n); // tính phi hàm Euler của n
void sievePhi(int n); // sàng phi hàm Euler từ 1 đến n
int mul(int a, int b); // tính (a * b) % MOD
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int a, b; cin >> a >> b;
sievePhi(b);
int phiA = calcPhi(a);
long long sum = 0;
for(int i = 1; i <= b; ++i){
int g = __gcd(a, i);
// phi(ab) = phi(a) * phi(b) * d / phi(d), g = UCLN(a, b)
sum = sum + ((1ll * phi[i] * phiA / phi[g] * g) % MOD);
sum %= MOD;
}
cout << sum;
return 0;
}
int calcPhi(int n){
int totient = n;
for(int i = 2; 1ll * i * i <= n; ++i){
if(n % i == 0){
while(n % i == 0) n /= i;
totient -= totient / i;
}
}
if(n != 1) totient -= totient / n;
return totient;
}
void sievePhi(int n) {
for (int i = 0; i <= n; ++i) phi[i] = i;
for (int i = 2; i <= n; ++i) {
if (phi[i] == i) {
for (int j = i; j <= n; j += i) {
phi[j] -= phi[j] / i;
}
}
}
}
int mul(int a, int b){
return (1ll * a * b) % MOD;
}
Độ phức tạp thuật toán bằng .
Tóm tắt đề: Cho nhiều số . Với mỗi số , tính giá trị của:
Tất nhiên, chương trình trâu sẽ không thể giải quyết bài toán này được. Ta cần tìm một tính chất nào đó của công thức trên giúp ta giải quyết bài toán nhanh hơn.
Đầu tiên, ta viết lại công thức như sau:
Với
Ta thấy, với , ta suy ra được rằng: .
Từ đây, hàm có thể được viết lại bằng với là các ước nguyên dương của .
Kết luận, với mỗi số , giá trị của công thức mà đề cho sẽ bằng:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
ll phi[N];
ll sum[N];
void init();
int main () {
ios_base::sync_with_stdio(0);
cin.tie(0);
init();
int n;
while(cin >> n, n){
cout << sum[n] << '\n';
}
return 0;
}
void init(){
for (int i = 0; i < N; ++i) phi[i] = i;
for (int i = 2; i < N; ++i) {
if (phi[i] == i) {
for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
}
}
for(int i = 1; i < N; ++i){
for(int j = 2; i * j < N; ++j){
sum[i * j] += i * phi[j];
}
sum[i] += sum[i - 1];
}
}
Độ phức tạp thuật toán sẽ là cho việc tính tất cả các trường hợp của , và cho mỗi số trong các truy vấn.