【SPJ6285 NGM2 - Another Game With Numbers】题解

题目链接：https://www.luogu.org/problemnew/show/SP6285

唉好久之前校内模拟赛的题目

嘴上说着明白但是实现起来我的位运算太丑陋了啊！

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int maxn = 300;

ll n, k, a[maxn], ans;

ll gcd(ll x, ll y)

{

	if(x % y == 0) return y;

	else return gcd(y, x%y);

}

ll lcm(ll x, ll y)

{

	return x / gcd(x,y) * y;

}

int main()

{

	ios::sync_with_stdio(false);

	cin>>n>>k;

	for(ll i = 0; i < k; i++) cin>>a[i];

	for(ll i = 1; i < (1 << k); i++)

	{

		ll res = 1, flag = 0;

		for(ll j = 0; j < k; j++)

		{

			if(i & (1 << j))

			{

				res = lcm(res, a[j]);

				flag++;

			}

		}

		if(flag & 1) ans += (n/res);

		else ans -= (n/res);

	}

	cout<<n-ans;

	return 0;

}

巴特西

【SPJ6285 NGM2 - Another Game With Numbers】题解

最新文章

热门文章

巴特西

【SPJ6285 NGM2 - Another Game With Numbers】 题解

最新文章

热门文章

【SPJ6285 NGM2 - Another Game With Numbers】题解