紫书习题 10-44 UVa 11246 ( 容斥原理）

2024-08-31 15:32:59

把k的倍数的删去（k, 2k, 3k……），但是k^2不应该删去，因为k已经删去，所以不存在某个数乘上k之后为k^2

所以k^2可以留下，然后因为有k^2，所以k^3就是k^2的k倍，所以k^3要删去，但是k^4又要加回来，以此类推

ans = n - n / k + n / (k^2) - n / (k^3)……

见代码

#include<cstdio>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

int solve(int n, int k)

{

	int sign = 1, ans = 0;

	while(n)

	{

		ans += sign * n;

		n /= k;

		sign *= -1;

	}

	return ans;

}

int main()

{

	int n, k, T;

	scanf("%d", &T);

	while(T--)

	{

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

		printf("%d\n", solve(n, k));

	}

	return 0;

}

最新文章

热门文章