萌新初学OI,求助莫比乌斯函数
  • 板块学术版
  • 楼主2huk
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/5/18 08:01
  • 上次更新2023/10/23 15:28:05
查看原帖
萌新初学OI,求助莫比乌斯函数
748509
2huk楼主2023/5/18 08:01

rt,请问大佬们莫比乌斯函数是完全积性函数吗?

bdfs上大多数都没有回答,有一篇博客里说不是,但我自己测了几组发现应该是的。

这是我自己测试的代码:

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 1e6 + 10;

int mu[N], p[N], cnt;
bool st[N]; 

void prime(int n)
{
	mu[1] = 1;
	for (int i = 2; i <= n; i ++ )
	{
		if (!st[i]) p[ ++ cnt] = i, mu[i] = -1;
		for (int j = 1; p[j] <= n / i; j ++ )
		{
			st[p[j] * i] = 1;
			if (i % p[j]) mu[p[j] * i] = -mu[i];
			else
			{
				mu[i * p[j]] = 0;
				break;
			}
		}
	}
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

signed main()
{
	srand(time(0));
	prime(1e6);
	for (int i = 1; i <= 1e6; i ++ )
	{
		int a = rand() % 100;
		int b = rand() % 100;
		if (gcd(a, b) != 1) continue;
		if (mu[a] * mu[b] != mu[a * b])
		{
			cout << a << ' ' << mu[a] << '\n' << b << ' ' << mu[b] << '\n' << a * b << ' ' << mu[a * b] << '\n';
			break;
		}
	}
			
	return 0;
}

哪位大佬能回答一下!

2023/5/18 08:01
加载中...