題目是這樣子的

莫比烏斯函數，由德國數學家和天文學家莫比烏斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作為莫比烏斯函數的記號。（據說，高斯(Gauss)比莫比烏斯早三十年就曾考慮過這個函數）。 具體定義如下： 如果一個數包含平方因子，那么miu(n) = 0。例如：miu(4), miu(12), miu(18) = 0。 如果一個數不包含平方因子，并且有k個不同的質因子，那么miu(n) = (-1)^k。例如：miu(2), miu(3), miu(30) = -1,miu(1), miu(6), miu(10) = 1。 給出一個數n, 計算miu(n)。Input 輸入包括一個數n，(2 <= n <= 10^9) Output 輸出miu(n)。 Sample Input 5 Sample Output -1

這題時間限制是1s，因此無法通過先建立質數表然后再查詢的方法進行，因此需要直接分解質因數。

#include <iostream> #include <math.h> using namespace std; typedef long long ll; #define MAXN 10e9 + 10ll miu(ll n) {ll miu = 0;ll prime_js = 1;bool has_n2_factor = false;for(int i=2;i*i<=n;i++){int cnt=0;if(has_n2_factor) break;if(n%i==0){prime_js++;//質因子出現次數加1while(n%i==0){n/=i;cnt++;//記錄該質因子出現的次數}if(cnt>=2) has_n2_factor=true;}}if(has_n2_factor) miu = 0;else{miu = pow(-1,prime_js);}return miu; }int main() {ll n;cin >> n;cout << miu(n) << endl;//system("pause"); }

總結

以上是生活随笔為你收集整理的【因式分解】莫比乌斯函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。