学步园

红果果的容斥定理。

代码如下：

#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int ans, seq[15], N, flag;

int M;

inline int GCD(int a, int b)
{
    int t;
    while (b) {
        t = a;
        a = b;
        b = t % b;
    }
    return a;
}

inline int LCM(int a, int b) 
{
    return a / GCD(a, b) * b;
}

void dfs(int p, int num, int sign)
{
    if (p > 0) {
        ans += sign * N / num;
    }
    for (int i = p + 1; i <= M; ++i) { 
        dfs(i, LCM(seq[i], num), -sign);
    }
}

int main()
{
    int i, j;
    while (scanf("%d %d", &N, &M) == 2) {
        flag = 0;
        ans = 0; 
        for (i = 1, j = 1; i <= M; ++i, ++j) {
            scanf("%d", &seq[j]);
            if (seq[j] <= 0 || seq[j] >= N) {
                --j;
            }
        }
        N -= 1;
        M = j - 1;
        dfs(0, 1, -1);
        printf("%d\n", ans);
    }    
    return 0;
}