莫比乌斯函数

1240 莫比乌斯函数
亚洲必赢官网app，标准时间限制：1 秒 空间范围：131072 KB 分值: 0 难度：基础题 收藏 关切
莫比乌斯函数，由德意志联邦共和国地理学家和天国学家莫比乌斯提议。梅滕斯(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)。
Input示例
5
Output示例
-1

思路：在线求μ(d)

代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll mubi(ll n) {
 5     ll mu=1;
 6     for(ll i=2;i*i<=n;++i) {
 7         if(n%i==0) {
 8             mu*=-1;
 9             ll k=0;
10             do {
11                 k++;
12                 if(k>1) {
13                     mu=0;break;
14                 }
15                 n/=i;
16             }while(n%i==0);
17         } 
18     }
19     if(n>1) mu*=-1;
20     return mu;
21 }
22 int main() {
23     ios::sync_with_stdio(false);
24     ll n;
25     cin>>n;
26     cout<<mubi(n)<<endl;
27     return 0;
28 }

View Code