长春企业建站平台,区总工会网站建设流程,上线了怎么做网站,企业商城网站建设开发Mobius函数定义为#xff0c;输入一个正整数N#xff0c;当N1时#xff0c;函数值为1#xff0c;当N不为1时#xff0c;首先在稿纸上将它分解质因数#xff0c;若某质因数的个数大于1#xff0c;则函数值为0#xff0c;如N45#xff0c;453*3*5,3出现了两次#xff0…Mobius函数定义为输入一个正整数N当N1时函数值为1当N不为1时首先在稿纸上将它分解质因数若某质因数的个数大于1则函数值为0如N45453*3*5,3出现了两次故函数值为0。若质因数全都不相同设有p个则函数值为-1的p次方如78,782*3*13质因数全都不相同有3个所以函数值为-1的3次方为-1。 f(n)和g(n)是定义在正整数集合上的两个函数若 则 反之亦然。 其中 μ(d)1, 若d偶数个不同素数之积 μ(d)(-1)r, 若d奇数个不同素数之积 μ(d)0, 其他例如μ( 30) μ( 2·3·5 ) (1)3μ(12) μ( 3·22) 0对任何素数p,μ(p)-1辅助定理 编辑对于任意正整数n恒有 代码模板 #include stdio.h
// 一个数字可以有的最多不同质因数个数
#define MAX_PRIM_FACTOR_AMOUNT 1000 /*
Mobius 函数定义为输入一个正整数N当N1时函数值为1当N不为1时首先在稿纸上将它分解质因数。若某质因数的个数大于1则函数值为0如N45453*3*5,3出现了两次故函数值为0。若质因数全都不相同设有p个则函数值为-1的p次方如78,782*3*13质因数全都不相同有3个所以函数值为-1的3次方为-1。
*/
/*功能求 Mobius 函数的值参数n 一个正整数 doPrint 是否输出正整数 n 的质因数分解形式。1输出0不输出。 返回 Mobius 函数的值
*/
int Mobius(unsigned int n, unsigned int doPrint)
{// 用 m 来临时保存 m 的值。因此 n 的值在运算过程中会被改变。 int m n; // 用 i 来枚举 n 的质因数int i;// 数字 n 的不同质因数个数 int primeFactorAmount 0;// n 的某个质因数 i出现在 n 中的次数 int countCurrentPrimeFactor 0;// Mobius 函数的值。初始值为 -3表示还没有计算出函数值。 int result -3;// 记录所有质因数出现的次数。用于输出质因数分解形式。 int primFactors[MAX_PRIM_FACTOR_AMOUNT][2]; if(n 0){// 【1】n0 的情况实际是非法的输入。这里返回 -2。 result -2;}else if(n 1){// 【2】n1 的情况result 1;}else{for(i2; in ; i){countCurrentPrimeFactor 0;while(n % i 0){// 从数字 n 中除去质因数 i n / i;// 统计质因数 i 出现的次数 countCurrentPrimeFactor ;}if(countCurrentPrimeFactor 1){// 数字 i 是数字 n 的质因数 primFactors[primeFactorAmount][0] i;primFactors[primeFactorAmount][1] countCurrentPrimeFactor;primeFactorAmount ;if(countCurrentPrimeFactor 1){// 【3】 n 的某质因数的个数大于 1 的情况 result 0;} }}if(result -3){// 【4】 n 有 p 个不同的质因数返回 (-1)^p result (primeFactorAmount%2 ? -1 : 1); } }if(doPrint){// 需要输出 n 的质因数分解形式if(m 1)printf(%d %d\n, m , m);else{printf(%d , m);for(i0; iprimeFactorAmount; i){printf(%d, primFactors[i][0]);if(primFactors[i][1] 1)// 质因数出现多余一次输出出现次数。 printf(^%d, primFactors[i][1]);if(i (primeFactorAmount-1))printf( * );}printf(\n);} } return result;}
int main(int argc, char *argv[])
{int n;// 输入 n 按 ctrl z 停止输入 while(scanf(%d,n) !EOF){printf(Mobius(%d) %d\n, n, Mobius(n, 1));} return 0;
}/*
测试数据
0
1
45
78
12345678测试结果
0
0 0
Mobius(0) -2
1
1 1
Mobius(1) 1
45
45 3^2 * 5
Mobius(45) 0
78
78 2 * 3 * 13
Mobius(78) -1
12345678
12345678 2 * 3^2 * 47 * 14593
Mobius(12345678) 0
^Z
*/
