Cho một số n; nhiệm vụ là tìm hàm Mobius của số n.
Chức năng Mobius là gì?
Một hàm Mobius là một hàm lý thuyết số được định nghĩa bởi
$$ \ mu (n) \ Equiv \ begin {case} 0 \\ 1 \\ (- 1) ^ {k} \ end {case} $$
n =0 Nếu n có một hoặc nhiều hơn một yếu tố lặp lại
n =1 Nếu n =1
n =(-1) k 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 tiếp cận mà chúng tôi sẽ sử dụng để giải quyết vấn đề đã cho -
- Lấy một đầu vào N.
- Lặp lại i từ 1 đến nhỏ hơn N để kiểm tra số chia hết của N và kiểm tra xem nó có phải là số nguyên tố hay không.
- Nếu cả hai điều kiện thỏa mãn, chúng tôi sẽ kiểm tra xem bình phương của số cũng chia cho N thì kết quả trả về là 0.
- Nếu không, chúng tôi tăng số lượng các thừa số nguyên tố, nếu số đếm là số chẵn thì trả về 1 số khác nếu số đó là số 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ụ
#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;
// For a prime factor i check if i^2 is also
// a factor.
for ( i = 1; i <= N; i++) {
if (N % i == 0 && isPrime(i)) {
// Check if N is divisible by i^2
if (N % (i * i) == 0)
return 0;
else
// i occurs only once, increase p
p++;
}
}
// All prime factors are contained only once
// Return 1 if p is even else -1
return (p % 2 != 0)? -1 : 1;
}
// Driver code
int main() {
int N = 17;
cout << mobius(N) << endl;
} Đầu ra
N = -1