HNOI 2002 跳蚤 容斥，莫比乌斯反演
题意
一只跳蚤目前站在无限长的绳索中央，给出一张卡牌，上面有(n+1) 个自然数，其中最后一个数字为(m) 。
跳蚤可以选择卡牌给的数字跳任意次，只要最终能够到达左边(1) 单位即可。
现在给定(n,m) ，问有多少张卡牌可以满足要求
[n,mleq 10^8,m^nleq 10^{16}
]
分析
一张牌能够跳到最左端，需要满足
[sum a_ix_i = 1
]
根据裴蜀定理，该方程要有解等价于
[(a_1,a_2...a_n,a_{n+1})=1
]
那么答案就可以写成
[sum _{a_1=1}^msum _{a_2=1}^m...sum _{a_n=1}^m[gcd(a_1,a_2...a_n,m) = 1]
\
=sum _{a_1=1}^msum _{a_2=1}^m...sum _{a_n=1}^m epsilon(gcd(a_1,a_2...a_n,m))
\
=sum _{a_1=1}^msum _{a_2=1}^m...sum _{a_n=1}^m sum _{d|a_i,d|m} mu(d)
\
=sum _{d|m} mu(d)cdot (frac{m}{d})^n
]
复杂度(O(sqrt{m}logn))
注意这里实现，如果暴力求出莫比乌斯函数，再枚举(m) 的因子复杂度会达到(O(m))
所以求这个表达式的时候考虑莫比乌斯函数的性质，只需要考虑其中的质因子，然后(dfs) 一下质因子的贡献，复杂度就降到了(O(2^{f(m)})) ,其中(f) 表示质因子的个数
代码
int cnt;
ll res;
int n, m;
int pri[20];
void dfs(int cur, int p, int mu) {
if (cur == cnt) {
res += mu * ksm(m / p, n);
return;
}
dfs(cur + 1, p, mu);
dfs(cur + 1, p * pri[cur], -mu);
}
int main() {
n = readint();
m = readint();
int k = m;
for (int i = 2; i * i <= m; i++) {
if (k % i == 0) {
pri[cnt++] = i;
while (k % i == 0) k /= i;
}
}
if (k != 1) pri[cnt++] = k;
dfs(0, 1, 1);
Put(res);
}