五校联考 running （欧拉函数）

五校联考 running （欧拉函数） 题面

$ solution: $

讲真吧，这道题真的出得，嗯，太恐怖了。

考场上这道题真的把我看懵了，这道题以前是见过的，但欧拉函数？我学过吗？一道容斥都要超时的题目，我都要为我自己点根香了，拿着gcd一顿乱搞，果然搞出了个0分。

不得不承认博主的数学真的太渣了，但这道题的解题思路真的太妙了（因为渣所以必须学习！）。

首先，一个必须要知道的东西， *** 场是环形的（即 \(（mod~n）\) 意义下的）。

若第$ k $个格子可以被第 $ i $ 个同学踩到，那么必定存在一个 $ x $ 使 $ x\times a_i $ 在 \(（mod~n）\)之后等于 $ k $ ！而这也就相当于：存在一对 $ x $ 和 $ y $ 使得 $ x\times a_i-y*n=k $

而这也就牵扯到我们整除的一些性质了，要满足上面这个式子有整数解，充要条件是 $ (a_i,n)|k $ 也就是说所有能被 $ (a_i,n) $ 整除的格子都可以被第 $ i $ 位同学踩到！！！可是这样的话，有可能一个格子会被多个同学踩到，我们怎么去重呢？

我们发现产生重复的原因是我们的充要条件即 $ (a_i,n)|k （i\in m）$ ，有可能存在多个 $ i $ 能使条件成立，并存在多个 $ i $ 使它们的 $ (a_i,n) $ 存在公因数，然后我们考虑如何让重复的情况只出现一次：就是枚举\(n\)的约数（把 $ (a_i,n) $ 所有可能的值枚举一遍），枚举并判断它是否有贡献之后我们不算存在多少 $ k $ 可以整除它，我们只算有多少 $ (k,n) $ 能等于它。

（因为我们枚举的 $ n $ 的约数会包括它的倍数，当下我们只算好它的贡献！）

我们把枚举的约数定为 $ d $ ，那我们就只要求有多少个 $ k $ ，使 $ (k,n)=d $ ，也就是求有多少个 $ k $ ，使 $ (\frac{k}{d} ,\frac{n}{d})=1 $ 也就是求欧拉函数了。

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int n,m,top,ans;

int a[55];

int b[100005];

inline int qr(){

	char ch;

	while((ch=getchar())<'0'||ch>'9');

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res;

}

inline int gcd(int x,int y){

	if(!y)return x;

	return gcd(y,x%y);

}

inline int phi(int x){//单独求欧拉函数

	int y=x;

	for(rg i=2;i<=top&&x>1;++i){

		if(!(x%b[i]))y=y/b[i]*(b[i]-1);

		while(!(x%b[i]))x/=b[i];

	}return y;

}

int main(){

	//freopen("running.in","r",stdin);

	//freopen("running.out","w",stdout);

	ans=n=qr(),m=qr();

	for(rg i=1;i<=m;++i)a[i]=qr();

	for(rg i=1;i<=sqrt(n);++i)

		if(n%i==0)b[++top]=i,b[++top]=n/i;//枚举所有约数

	sort(b+1,b+top+1);

	for(rg i,k=1;k<=top;++k){

		i=b[k];

		for(rg j=1;j<=m;++j)

			if(i%gcd(a[j],n)==0)//如果这个约数有贡献（即存在一个人使得(ai,n)|k）

			    {ans-=phi(n/i);break;}

	} printf("%d\n",ans);

	return 0;

}