【数论】【容斥原理】【EXGCD】COCI? ?2017/2018 Round? ?#3 ? ?Sa?etak

分析：

非常板的容斥题。。。考场上时间多点应该还是写得出来的。。。

转换一下题目，就是求
满足$x\equiv 1(mod\ a_i)且x\equiv 0(mod\ a_j)$的x的个数（$x\leq N$）。

由于N非常大，无法判断求解，只能算贡献。

就是对于一对数$a_i,a_j$求$A*a_i=B*a_j+1$中A的解的个数。
然而算贡献最大的弊病就是会重复，所以要去重。

然后就可以用容斥原理。

定义$f_{(u,v)}$表示$\forall i\in u满足\ x\equiv 1(mod\ a_i)且\forall j\in v满足\ x\equiv 0(mod\ a_j)$

那么答案就是$\sum(-1)^{|u|+|v|}f(u,v)$

接下来就是求$f(u,v)$，可以用exgcd来算，因为$\forall i\in u满足\ x\equiv 1(mod\ a_i) \Rightarrow x\equiv1(mod\ lcm(a_0,a_1,a_2,……))$。

然后就变成$Ax=By+1$的解，就变成了$Ax-By=1$，然后就是exgcd的模板了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXM 22
#define MAXN 1100000
using namespace std;
typedef long long ll;
ll n;
ll f[MAXN],sum[MAXN],a[MAXN],sum1[MAXN];
int m;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);  
}
ll lcm(ll x,ll y){ll g=gcd(x,y);return x/g*y;
}
ll exgcd(ll x,ll y,ll g){if(g==0)return 0;ll t=exgcd(y%x,x,g%x);  t=(g-t*y)/x;if(t<0){t+=(-t)/y*y;t+=y;}return t%y;
}
int main(){SF("%lld%d",&n,&m);for(int i=0;i<m;i++)SF("%d",&a[i]);f[0]=1;for(int i=1;i<(1<<m);i++){int k1=(i&(-i));int k=-1;   while(k1){k1>>=1;k++;}int i1=(i^(1<<k));if(f[i1]==0)continue;f[i]=lcm(f[i1],a[k]);if(f[i]>n)f[i]=0;}for(int i=1;i<(1<<m);i++)for(int j=1;j<(1<<m);j++)if(f[i]&&f[j]&&gcd(f[i],f[j])==1){ll x=exgcd(f[i],f[j],1);ll res=f[i]*x;ll lcc=f[i]*f[j];if(res<n)sum[i|(j<<m)]=(n-res-1ll)/lcc+1ll;}ll ans=0;for(int i=1;i<(1<<(2*m));i++){int x=__builtin_popcount(i);if(x%2==0)ans+=sum[i];elseans-=sum[i];    }for(int i=0;i<m;i++)if(n%a[i]==1){ans++;break;}PF("%lld",ans);
}