math/mobius_mu.cpp

• View this file on GitHub
• Last update: 2021-06-22 23:29:40+09:00

Code

int mobius_mu(ll n) {
	int res = 0;
	for(ll d = 2; d*d <= n; d++) {
		if(n % (d*d) == 0) return 0;
		else if(n % d == 0) n /= d, res++;
	}
	if(n != 1) res++;
	return res&1 ? -1 : 1;
}

#line 1 "math/mobius_mu.cpp"
int mobius_mu(ll n) {
	int res = 0;
	for(ll d = 2; d*d <= n; d++) {
		if(n % (d*d) == 0) return 0;
		else if(n % d == 0) n /= d, res++;
	}
	if(n != 1) res++;
	return res&1 ? -1 : 1;
}

Back to top page