Description：

有 $n+1$ 张卡片，每张都在 $[1,m]$ 之间，且第 $n+1$ 张是 $m$ ，随机 $n+1$ 张卡片，有 $m^n$ 种不同的方案，求有多少个方案，满足可以线性组合出 $1$ 。

$1\leqslant n,m\leqslant 10^8$

Solution：

首先由裴蜀定理得要求的等价于： $$ \sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_3=1}^m[\gcd(i_1,i_2,\dots,i_n)=1] $$ 正难则反，考虑求 $\gcd$ 不为 $1$ 的序列数。

然后我们把 $m$ 分解质因数，设其中一个质数是 $p_i$ ，那么 $\gcd$ 是 $p_i$ 的倍数的序列数为 $(\frac m {p_i})^n$ ，大概就是每个数都必须是 $p_i$ 的倍数，这样的数在 $[1,m]$ 中有 $\frac m {p_i}$ 个。

肯定会算重，容斥一下就好了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

int pri[100000010],tot = 0;

void divide(int k)

{

	int s = k;

	for(int i = 2;i * i <= k;++i)

	{

		if(s % i == 0)

		{

			pri[++tot] = i;

			while(s % i == 0)s /= i;

		}

	}

	if(s != 1)pri[++tot] = s;

	return;

}

typedef long long ll;

ll ans = 0;

ll power(ll a,int b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a;

		a = a * a;

		b = b >> 1;

	}

	return res;

}

void calc(int pos,int type,ll val)

{

	if(val > m)return;

	if(pos == tot + 1)

	{

		ans += type * power(m / val,n);

		return;

	}

	calc(pos + 1,type,val);

	calc(pos + 1,-type,val * pri[pos]);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	divide(m);

	calc(1,1,1);

	cout << ans << endl;

	return 0;

}