A28690. 因数:也称约数，如果整数a除以整数b，商为整数且余数为0，则称b 是a的因数。例如:1、2、3、6 都是 6的因数。素数:也称质数，是指在大于1的自然数中，除了1和它本身以外没有其他因数的数。例如:2、3、5 是素数，4、6、8 不是素数平方数:指的是可以写成某个整数的平方的数。例如:4(22)、9(32)、16(42)都是平方数。莫比乌斯函数 μ(n) 是指以下的函数:1、若n=1，则 μ(n…
填空题
困难
知识点
题目描述
因数:也称约数，如果整数a除以整数b，商为整数且余数为0，则称b 是a的因数。
例如:1、2、3、6 都是 6的因数。素数:也称质数，是指在大于1的自然数中，除了1和它本身以外没有其他因数的数。例如:2、3、5 是素数，4、6、8 不是素数平方数:指的是可以写成某个整数的平方的数。例如:4(22)、9(32)、16(42)都是平方数。
莫比乌斯函数 μ(n) 是指以下的函数:
1、若n=1，则 μ(n)=1;
2、若 n的因数中有大于1的平方数，则 μ(n)=0;
3、若 n的因数中没有大于1的平方数，且n=p1,p2.....pk，则 μ(n)=(-1)k注:P,P.….P. 表示k(k<=1)个不同素数的乘积。
例如:
8 的因数有 1、2、4、8，其中大于1的平方数有 4，所以 μ(8)=0;
15 的因数有 1、3、5、15，没有大于1的平方数，且15=3*5，所以μ(15)=(-1)2= 1;
30 的因数有1、2、3、5、6、10、15、30，没有大于1的平方数，且30=2*3*5，所以μ(30)=(-1)3=-1。
给定两个正整数 m、n，请计算 m 到 n之间(含 m和n)所有整数的莫比乌斯函数值之和。
输入格式
一行输入两个正整数 m 和 n，整数之间以一个空格隔开
输出格式
输出一个整数，表示 m 到 n之间(含 m 和 n)所有整数的莫比乌斯函数值之和
输入样例
1 10
输出
-1
参考答案
#include<bits/stdc++.h>
using namespace std;
int m,n;
const int N=2e7+10;
int cnt[N],a[N],s[N];
bool t[N];
int main()
{
cin>>m>>n;
for(int i=2;i<=n/2;i++)
{
if(cnt[i]) continue;
for(int j=i*2;j<=n;j+=i)//埃筛，计算因子数量
cnt[j]++;
}
for(int i=2;i*i<=n;i++)
{
int c=i*i;
for(int j=c;j<=n;j+=c)//记录有完全平方数因子的数
t[j]=1;
}
a[1]=1;
for(int i=2;i<=n;i++)
{
if(t[i])continue; //有完全平方数因子 函数值为0
if(cnt[i]%2||cnt[i]==0)
a[i]=-1; //奇数个质因子 或者 质数 函数值-1
else
a[i]=1;
}
int ans=0;
for(int i=m;i<=n;i++)
ans+=a[i];
cout<<ans<<endl;
return 0;
}
上一题
下一题