【bzoj】2190 - 仪仗队（容斥原理）

FishWang

发布于 2025-08-27 09:01:37

6400

代码可运行

运行总次数：0

代码可运行

点击打开题目

2190: [SDOI2008]仪仗队

Time Limit: 10 Sec Memory Limit: 259 MB Submit: 2486 Solved: 1572 [ Submit][ Status][ Discuss]

Description

　　作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。　　

　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

　　共一个数N。

Output

　　共一个数，即C君应看到的学生人数。

Sample Input

　　4

Sample Output

　　9

HINT

【数据规模和约定】　　对于 100% 的数据，1 ≤ N ≤ 40000

点击打开链接

和上面那道题的思路一样，用容斥原理直接过了。

代码如下：

#include <cstdio>
#define MAX 40000
int p[40000];
int ant;
void pr(int x)
{
	ant = 0;
	for (int i = 2 ; i * i <= x ; i++)
	{
		if (x % i == 0)
		{
			p[ant++] = i;
			while (x % i == 0)
				x /= i;
		}
	}
	if (x > 1)
		p[ant++] = x;
}
long long solve(int n)
{
	long long ans = 0;
	for (int i = 1 ; i < (1 << ant) ; i++)
	{
		int v = 1;
		int m = 0;
		for (int j = 0 ; j < ant ; j++)
		{
			if (i & (1 << j))
			{
				v *= p[j];
				m++;
			}
		}
		if (m & 1)	
			ans += n / v;
		else
			ans -= n / v;
	}
	return ans;
}
int main()
{
	int n;
	long long ans;
	scanf ("%d",&n);
	n--;
	ans = 2 + n;
	for (int i = 2 ; i <= n ; i++)
	{
		pr(i);
		ans += n - solve(n);
	}
	printf ("%lld\n",ans);
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

int