Cho một số n; nhiệm vụ là tìm hàm Mobius của số n.
Hàm Mobius là gì?
Hàm Mobius là hàm lý thuyết số được định nghĩa bởi:
$$\mu(n)\equiv\begin{cases}0\\1\\(-1)^{k}\end{cases}$$
n = 0 Nếu n có một hoặc nhiều hơn một因數 lặp lại
n = 1 Nếu n = 1
n = (-1)ᵏ Nếu n là tích của k số nguyên tố phân biệt
Ví dụ
Input: N = 17 Output: -1 Explanation: Prime factors: 17, k = 1, (-1)^k 🠠(-1)^1 = -1 Input: N = 6 Output: 1 Explanation: prime factors: 2 and 3, k = 2 (-1)^k 🠠(-1)^2 = 1 Input: N = 25 Output: 0 Explanation: Prime factor is 5 which occur twice so the answer is 0
Phương pháp giải quyết:
- Nhập N.
- Duyệt i từ 1 đến nhỏ hơn N, kiểm tra số chia hết của N và xem nó có phải số nguyên tố không.
- Nếu cả hai điều kiện thỏa mãn, kiểm tra xem bình phương của số đó cũng chia hết N thì trả về 0.
- Ngược lại tăng đếm ước nguyên tố, nếu đếm chẵn trả về 1, lẻ trả về -1.
- In kết quả.
Thuật toán
Start Step 1→ In function bool isPrime(int n) Declare i If n < 2 then, Return false Loop For i = 2 and i * i <= n and i++ If n % i == 0 Return false End If Return true Step 2→ In function int mobius(int N) Declare i and p = 0 If N == 1 then, Return 1 End if Loop For i = 1 and i <= N and i++ If N % i == 0 && isPrime(i) If (N % (i * i) == 0) Return 0 Else Increment p by 1 End if End if Return (p % 2 != 0)? -1 : 1 Step 3→ In function int main() Declare and set N = 17 Print the results form mobius(N) Stop
Ví dụ mã nguồn
#include<iostream> using namespace std; // Function to check if n is prime or not bool isPrime(int n) { int i; if (n < 2) return false; for ( i = 2; i * i <= n; i++) if (n % i == 0) return false; return true; } int mobius(int N) { int i; int p = 0; //if n is 1 if (N == 1) return 1; // Với ước nguyên tố i kiểm tra i^2 có phải // ước của N không for ( i = 1; i <= N; i++) { if (N % i == 0 && isPrime(i)) { // Kiểm tra N có chia hết cho i^2 không if (N % (i * i) == 0) return 0; else // i chỉ xuất hiện một lần, tăng p p++; } } // Tất cả ước nguyên tố chỉ chứa một lần // Trả về 1 nếu p chẵn ngược lại -1 return (p % 2 != 0)? -1 : 1; } // Driver code int main() { int N = 17; cout << mobius(N) << endl; } Kết quả
N = -1