题目概述
求有多少种方案，满足当 \(a_i\in [1,m]\)，\(x_i\) 为任意整数时有：
\[m\times x_{n+1}+\sum_{i=1}^n x_ia_i=-1
\]
分析
根据裴蜀定理我们转化为只需满足：
\[\gcd(\gcd\{a_i\},m)=1
\]
的 \(a\) 的数量就是本题答案。
相当于求：
\[\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_n=1}^m[\gcd(\gcd\{a_i\},m)=1]
\]
显然可以用莫比乌斯函数替代为：
\[\sum_{a_1=1}^m\sum_{a_2=1}^m\dots\sum_{a_n=1}^m\sum_{d\mid \gcd(\gcd\{a_i\},m)}\mu(d)
\]
考虑先枚举 \(d\) 有：
\[\sum_{d\mid m}\mu(d)\sum_{a_1=1}^{\left \lfloor \frac{m}{n} \right \rfloor }\dots\sum_{a_n=1}^{\left \lfloor \frac{m}{n} \right \rfloor }1
\]
所以说：
\[ans=\sum_{d\mid m}\mu(d) \left(\left\lfloor\frac{m}{n}\right\rfloor\right)^n
\]
于是我们考虑如何快速求这个，因为暴力求约等于 \(\mathcal{O}(m)\) 的，但是比这个小，最贴切应该是 \(\mathcal{O}(d(m)\sqrt m)\)，好像能过。
下面给出两种处理方法。
第一种
注意到 \(\omega(10^8)=8\)，所以说，最多只有 \(8\) 个质因子，根据莫比乌斯函数的定义可以直接 \(2^8\) 暴力即可。
第二种
还是根据莫比乌斯函数的定义得到（设 \(m=\prod_{i=1}^k p_i^{\alpha_i}\)）：
\[ans = m^n-\sum_{i}\left(\frac m {p_i}\right)^n+\sum_{i\ne j}\left(\frac{m}{p_ip_j}\right)^n-\dots
\]
提取 \(m^n\) 有：
\[ans=m^n(1-\sum_{i}\frac{1}{p_i^n}+\sum_{i\ne j}\frac{1}{p_i^n p_j^n}\dots)=m^n\prod_i\frac{1}{p_i^n}
\]
注意：\(\prod_i\frac{1}{p_i^n}\) 展开后就是：\(1-\sum_{i}\frac{1}{p_i^n}+\sum_{i\ne j}\frac{1}{p_i^n p_j^n}\dots\)。
于是这道题目做完了。
代码
时间复杂度 \(\mathcal{O}(\sqrt m\log n)\)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define int long long
// #define N
using namespace std;
int qpow(int a,int b) {int res = 1;while(b) {if (b & 1) res = res * a;a = a * a;b >>= 1;}return res;
}
int n,m;
signed main() {cin >> m >> n;int fac = n,ans = 1;for (int i = 2;i * i <= n;i ++)if (n % i == 0) {ans *= qpow(i,m) - 1;fac /= i;while(n % i == 0) n /= i;}if (n != 1) ans *= qpow(n,m) - 1,fac /= n;ans = ans * qpow(fac,m);cout << ans;return 0;
}