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;
}
哪位大佬能回答一下!