Description：

给定 $n$ 和 $k$ 个整数，求 $mod\ n$ 加法下的群 $G$ 的一个子群 $G'$ ，满足 $a[1]\sim a[k-1]$ 都不在群中而 $a[k]$ 在群中。

$1\leqslant n\leqslant 10^{14},1\leqslant k\leqslant 250000$

Solution：

题意就是找尽量多的 $[0,n)$ 内的数使得 $a[k]$ 在其中而 $a[1]\sim a[k-1]$ 不能由他们在模 $n$ 意义下线性组合出。

考虑怎么在模 $n$ 意义下线性组合出 $x$ ，发现只要存在 $\gcd(x,n)$ 或者他的约数再翻倍就可以了，于是把每个数和 $n$ 的 $\gcd$ 求出来，划掉这个数和它的约数， $n$ 的剩下的约数的所有倍数构成的集合大小就是答案。

怎么求这个有一个经典的 $2^k$ 的容斥做法，但是这个题显然是不能这么做的，有一个引理，就是剩下的数中最小的数一定是所有其他的数的约数，因为如果 $x$ 和 $y$ 都被选中了，那么 $\gcd(x,y)$ 一定要选中，因为由裴蜀定理得 $ax+by=c\times\gcd(x,y)$ 有解，也就是说 $x$ 和 $y$ 可以在模 $n$ 意义下线性组合出 $\gcd(x,y)$ ，既然 $x$ 和 $y$ 不能线性组合出所有其他的数，那么 $\gcd(x,y)$ 也一定可以，所以把这个找出来 $n/g$ 就是答案。

保证 $a[k]$ 在群中的做法很妙，包含 $a[k]$ 其实只要包含 $\gcd(a[k],n)$ 即可，就是把 $\gcd(a[k],n)$ 看成 $n$ ，把它分解因数再处理，这样做出来的就是在模 $\gcd(a[k],n)$ 意义下 $a[1]\sim a[k-1]$ 不能由他们线性组合出的答案，这个是一定包含 $\gcd(a[k],n)$ 的，所以一定包含 $a[k]$ ，最后统计用 $n$ 除就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

int k;

#define MAXN 250010

ll a[MAXN];

#define MAXD 10000010

ll fac[MAXD],tot = 0;

bool v[MAXD];

ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b,a % b));}

int main()

{

	scanf("%lld%d",&n,&k);

	for(int i = 1;i <= k;++i)scanf("%lld",&a[i]);

	ll g = gcd(a[k],n);

	for(ll i = 1;i * i <= g;++i)

	{

		if(g % i == 0)

		{

			fac[++tot] = i;

			if(i * i != g)fac[++tot] = g / i;

		}

	}

	sort(fac + 1,fac + 1 + tot);

	for(int i = 1;i < k;++i)

	{

		ll w = gcd(a[i],g);

		int p = lower_bound(fac + 1,fac + 1 + tot,w) - fac;

		v[p] = true;

	}

	for(int i = tot;i >= 1;--i)

	{

		if(!v[i])continue;

		for(int j = 1;j < i;++j)

		{

			if(fac[i] % fac[j] == 0)

			{

				v[j] = true;

			}

		}

	}

	for(int i = 1;i <= tot;++i)

	{

		if(!v[i])

		{

			cout << n / fac[i] << endl;

			break;

		}

	}

	return 0;

}