莫比乌斯函数
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