算法标签：

容斥原理

解题思路:

很明显的题目需要求解这么一个方程的解a[1]*x1+a[2]*x2+a[3]*x3+…+a[n]*xn+a[n+1]*m=1 (0<=a[i]<=m) 显然 满足方程式的解需要只需要满足 gcd(a[1],a[2],a[3]….a[n+1])==1 就行了

然后求解的过程就容易多了 就只求解M^N-gcd！=1 的方案数就行了

之后只要把M质因子分解 容斥一下就行了

引用这里

许多博客都举了这么一个例子：

例如:n=2,m=360 360=3^22^35 所有不满足条件的数列，最大公约数是360质因子的乘积，只要将这些组合去掉，就是要求的答案(不懂的慢慢揣摩)

那么就要先求出m的所有质因子，然后求出总的排列组合的个数，即题目中说的M^N，最后根据鸽巢原理求得最后答案。

公式为：ans=M^N-(有奇数个公因数的n元组)+(有偶数个公因数的n元组)。拿上面的例子来说就是

ans=m^n-( 有公因数2的n元组)- (有公因数3的n元组)- (有公因数5的n元组)+ (有公因数2，3的n元组) +(有公因数2，5的n元组)+ (有公因数3，5的n元组)- (有公因数2，3，5的n元组).

有公因数d的n元组，每个位置上有 (m/d)个选择（1 ~ m里面有m/d个d的倍数），根据乘法原理，可以得出有公因数d的n元组有 (m/d)^n 个.

#include <iostream>
typedef long long ll;
using namespace std;
const int N = 1e5;

int a[N];
//快速幂
ll pow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * a;
        n >>= 1;
        a *= a;
    }
    return res;
}

int main() {
    ll n, m, mm;
    cin >> n >> m;
    mm = m;
  //分解质因子
    int k = 0;
    for (int i = 2; i * i <= m; i++) {
        if (m % i == 0) {
            a[k++] = i;
            while (m % i == 0) m /= i;
        }
    }
    if (m > 1) a[k++] = m;
  //容斥原理
    ll ans = pow(mm, n);
    for (int i = 1; i < (1 << k); i++) {
        ll s = 1, kk = 0;
        for (int j = 0; j < k; j++) {
            if (1 & (i >> j)) {
                s *= a[j];
                kk++;
            }
        }
        s = pow(mm / s, n);
        if (kk & 1) ans -= s;
        else ans += s;
    }
    cout << ans << endl;
    return 0;
}