[noip模拟赛]跑跑步

容斥 数论 结论

---

题面

小胡同学是个热爱运动的好孩子。
每天晚上,小胡都会去操场上跑步,学校的操场可以看成一个由$n$个格子排成的一个环形,格子按照顺时针顺序从$0$到$n−1$标号。
小胡观察到有$m$个同学在跑步,最开始每个同学都在起点(即$0$号格子),每个同学都有个步长$a_i$,每跑一步,每个同学都会往顺时针方向前进$a_i$个格子。
由于跑道是环形的,如果一个同学站在$n−1$这个格子上,如果他前进一个格子,他就会来到$0$。
他们就这样在跑道上上不知疲倦地跑呀跑呀。
小胡同学惊奇地发现,似乎有些格子永远不会被同学跑到,他想知道这些永远不会被任何一个同学跑到的格子的数目,你能帮帮他吗?(我们假定所有同学都跑到过$0$号格子)。

• $n\leq10^9,m\leq50$

解析

因没打表猜结论被踩系列
首先要知道一个结论，即第$i$个同学能走到的格子一定是$k*gcd(a_i,n)$。（也许需要打表）

然后容斥一下就行了。
但是复杂度不太对劲啊。好像只能过$60pts$。

考虑优化。
于是我把$50$个数中的倍数去掉，从大到小排序让它尽早乘爆，加了诸多此类优化。似乎续到了$90pts$。
然后看看这玩意儿

il void dfs(re int x,re ll tot,re int num)
{
  if(tot>n) return;
  if(x>m)
    {
      if(num&1) ans-=(n/tot);else ans+=(n/tot);
      return;
    }
  fp(i,0,1)
    if(i) dfs(x+1,lcm(a[x],tot),num+1);else dfs(x+1,tot,num);
}

如果$lcm(a[x],tot)==tot$，那左右两边的结果不是能一正一负恰好抵消吗？
加上这个优化，就快得不行了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=100;
int n,m;
ll ans,a[N],tot;
bool vis[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll lcm(re ll x,re ll y){return x*y/__gcd(x,y);}
il bool cmp(re ll x,re ll y){return x>y;}
il void dfs(re int x,re ll tot,re int num)
{
  if(tot>n) return;
  if(x>m)
    {
      if(num&1) ans-=(n/tot);else ans+=(n/tot);
      return;
    }
  if(tot%a[x]==0) return;
  fp(i,0,1)
    if(i) dfs(x+1,lcm(a[x],tot),num+1);else dfs(x+1,tot,num);
}
int main()
{
  freopen("running.in","r",stdin);
  freopen("running.out","w",stdout);
  n=gi();m=gi();
  fp(i,1,m) a[i]=__gcd(gi(),1ll*n);
  sort(a+1,a+1+m,cmp);//然后被xzy造了个第i个数为2^i的数据卡了。。。
  dfs(1,1,0);
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

再看看标算。
只要枚举$n$的约数,令当前枚举到的数为$d$,若存在一个$i$,使得$gcd(a_i,n)|d$。说明所有$gcd(i,n)=d$的格子都能被到达,答案加上$\phi(\frac{n}{d})$即可。
证明：

$$\sum_{i=1}^n[gcd(i,n)==d]=\sum_{i=1}^{n/d}[gcd(i,n)==1]=\phi(\frac{n}{d})$$

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
int n,m,a[55],ans;
int phi(int x){
    int res=x;
    for (int i=2;i*i<=x;++i)
        if (x%i==0){
            res/=i;res*=i-1;
            while (x%i==0) x/=i;
        }
    if (x>1) res/=x,res*=x-1;
    return res;
}
void cal(int x){
    for (int i=1;i<=m;++i) if (x%a[i]==0) return;
    ans+=phi(n/x);
}
int main(){
    freopen("running.in","r",stdin);
    freopen("running.out","w",stdout);
    n=gi();m=gi();
    for (int i=1;i<=m;++i) a[i]=__gcd(n,gi());
    for (int i=1;i*i<=n;++i)
        if (n%i==0){
            cal(i);if (i*i<n) cal(n/i);
        }
    printf("%d\n",ans);return 0;
}