题目描述

小胡同学是个热爱运动的好孩子。

每天晚上，小胡都会去操场上跑步，学校的操场可以看成一个由n 个格子排成的一个环形，格子按照顺时针顺序从0 到n-1 标号。

小胡观察到有m 个同学在跑步，最开始每个同学都在起点（即0 号格子），每个同学都有个步长ai，每跑一步，每个同学都会往顺时针方向前进ai 个格子。由于跑道是环形的，如果

一个同学站在n-1 这个格子上，如果他前进一个格子，他就会来到0。

他们就这样在跑道上上不知疲倦地跑呀跑呀。小胡同学惊奇地发现，似乎有些格子永远不会被同学跑到，他想知道这些永远不会被任何一个同学跑到的格子的数目，你能帮帮他吗？（我们假定所有同学都跑到过0 号格子）。

输入

第一行两个整数n,m。

接下来一行有m 个正整数，代表a1; a2……am

输出

输出一个整数，代表永远不会被同学跑到的格子的数目。

样例输入

6 1

2

样例输出

3

数据范围

对于30% 的数据，1<=n<=100

对于60% 的数据，1<=n<=10^6

对于100% 的数据，1<=n<=10^9; 1<=m<=50; 1<=ai<=n

解法

显然，对于每个数a[i]，实际走过k∗gcd(a[i],n)这些格。

设c[i]=gcd(a[i],n)，显然可以筛去所有c[j]|c[i](j∈[1,n])。

然后使用容斥原理解决即可。

理论复杂度为O(2^m)，而m为50，显然超时。

而实际数据中，上界并没有那么高。

优化：

在使用容斥原理时；

dfs(v,1,lcm)−>dfs(v+1,1,lcm),dfs(v+1,−1,lcm∗a[v+1]/gcd(lcm,a[v+1]))

如果lcm=lcm∗a[v+1]/gcd(lcm,a[v+1])，那么显然两个转移出去的状态互为相反贡献，所以可直接退出。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define ln(x,y) ll(log(x)/log(y))

#define sqr(x) ((x)*(x))

using namespace std;

const char* fin="running.in";

const char* fout="running.out";

const ll inf=0x7fffffff;

const ll maxn=57;

ll n,m,i,j,k,ans=0,cnt,tmp;

ll a[maxn],c[maxn];

bool bz[maxn];

ll gcd(ll a,ll b){

    if (b) return gcd(b,a%b);

    else return a;

}

ll lcm(ll a,ll b){

    return a*b/gcd(a,b);

}

void dfs(ll v,ll flag,ll tmp){

    ll i,j,k;

    if (v==c[0]) {

        if (cnt) ans+=flag*(n/tmp);

        return;

    }

    if (lcm(tmp,c[v+1])==tmp) return;

    dfs(v+1,flag,tmp);

    cnt++;

    dfs(v+1,-flag,lcm(tmp,c[v+1]));

    cnt--;

}

int main(){

    freopen(fin,"r",stdin);

    freopen(fout,"w",stdout);

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

    for (i=1;i<=m;i++){

        scanf("%d",&a[i]);

        a[i]=gcd(a[i],n);

    }

    for (i=1;i<=m;i++){

        bool bz=false;

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

            if (a[i]%a[j]==0){

                bz=true;

                break;

            }

        if (!bz){

            c[++c[0]]=a[i];

        }

    }

    dfs(0,-1,1);

    ans=n-ans;

    printf("%lld",ans);

    return 0;

}

启发

容斥原理中，如果转移出去的两个状态互反，那么可退出。