51Nod 1240 莫比乌斯函数

By admin in 亚洲必赢官网app on 2018年10月15日

1240 莫比乌斯函数
标准化时间限制: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)

代码:

亚洲必赢官网app 1亚洲必赢官网app 2

 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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2018 亚洲必赢手机官网 版权所有