1796.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include <iostream>
#include <vector>
using namespace std;

int m;
__int64 n, sum;

vector<__int64> num;

__int64 gcd(__int64 a, __int64 b)
{
	__int64 t;
	if (a > b)
	{
		t = a, a = b, b = t;
	}
	if (a == 0)
	{
		return b;
	}
	else
	{
		return gcd(a, b % a);
	}
}

void dfs(int now, int all, __int64 multi)
{
	if (now >= num.size())
	{
		if (all == 0)
		{
			return;
		}
		if (all % 2)
		{
			sum += n / multi;
		}
		else
		{
			sum -= n / multi;
		}
		return;
	}
	dfs(now + 1, all, multi);
	dfs(now + 1, all + 1, multi * num[now] / gcd(multi, num[now]));
}

int main()
{
    int i;
	__int64 d;
    while (scanf("%I64d %d", &n, &m) == 2)
    {
		sum = 0;
		num.clear();
        for (i = 0; i < m; i++)
        {
            scanf("%I64d", &d);
			if (d)
			{
				num.push_back(d);
			}
        }
		dfs(0, 0, 1);
		for (i = 0; i < num.size(); i++)
		{
			if (n % num[i] == 0)
			{
				sum--;
				break;
			}
		}
		printf("%I64d\n", sum);
    }
    return 0;
}