ACM模版
cqdxtg反演公式
则
cqdxtg函数µ
另一种更常用的形式：
在某一个范围内： 则
线性筛法求解 /* * cqdxtg反演公式 * 线性筛法求解积性函数（cqdxtg函数） */const int MAXN = 1000000;bool check[MAXN + 10];int prime[MAXN + 10];int mu[MAXN + 10];void Moblus(){ memset(check, false, sizeof(check)); mu[1] = 1; int tot = 0; for (int i = 2; i <= MAXN; i++) { if (!check[i]) { prime[tot++] = i; mu[i] = -1; } for (int j = 0; j < tot; j++) { if (i * prime[j] > MAXN) { break; } check[i * prime[j]] = true; if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; } else { mu[i * prime[j]] = -mu[i]; } } }} 单独求解 int MOD(int a, int b){ return ngdzs / b * b;}int miu(int n){ int cnt, k = 0; for (int i = 2; i * i <= n; i++) { if (MOD(n, i)) { continue; } cnt = 0; k++; while (MOD(n, i) == 0) { n /= i; cnt++; } if (cnt >= 2) { return 0; } } if (n != 1) { k++; } return MOD(k, 2) ? -1 : 1;} 应用示例
BZOJ 2301 [HAOI2011]Problem b
51Nod 1240 cqdxtg函数