题目：

洛谷2926

(截止至本博客发表时，BZOJ1607题面有误，正确题面请到洛谷2926查看）

分析：

一句话题意：给定\(n\)个数\(\{a_i\}\)，求对于每个\(a_i\)有多少个数\(a_j\)满足\(a_i|a_j\) \((1\leq i,j\leq n\)且\(i \neq j)\)

按题意模拟的话\(O(n^2)\)肯定过不去。考虑对于一个数\(a_i\)，它仅会对所有\(a_i*k(1 \leq k\)且\(k\)为整数) 产生1的贡献。于是可以用\(M/a_i(M=max(\{a_i\}))\)的时间给所有\(ans[a_i*k]\)加上1 (\(ans[x]\)表示有多少个\(a_i\)能整除\(x\)) ，据说这样的复杂度是\(O(n\log n)\)的

注意可能有多个\(a_i\)相等，枚举\(a_i\)可能会多次执行相同的操作，费时间。用\(cnt[x]\)记录有多少个\(i\)满足\(a[i]=x\)。枚举\(x\)，每个\(x\)对\(kx\)的贡献是\(cnt[x]\)

以及一头牛不会拍自己的头，所以最终答案是\(ans[a_i]-1\)(详见代码)

代码：

#include <cstdio>

using namespace std;

namespace zyt

{

	const int M = 1e6 + 10, N = 1e5 + 10;

	void work()

	{

		static int ans[M], cnt[M], arr[N];

		int n;

		scanf("%d", &n);

		for (int i = 1; i <= n; i++)

		{

			scanf("%d", &arr[i]);

			cnt[arr[i]]++;

		}

		for (int i = 1; i <= M; i++)

			if (cnt[i])

				for (int j = i; j <= M; j += i)

					ans[j] += cnt[i];

		for (int i = 1; i <= n; i++)

			printf("%d\n", ans[arr[i]] - 1);

	}

}

int main()

{

	zyt::work();

	return 0;

}

巴特西

【洛谷2926/BZOJ1607】[USACO08DEC]Patting Heads拍头（筛法）

题目：

洛谷2926

(截止至本博客发表时，BZOJ1607题面有误，正确题面请到洛谷2926查看）

分析：

代码：

最新文章

热门文章

巴特西

【洛谷2926/BZOJ1607】[USACO08DEC]Patting Heads拍头（筛法）

题目：

洛谷2926

(截止至本博客发表时，BZOJ1607题面有误，正确题面请到洛谷2926查看） 分析：

代码：

最新文章

热门文章

(截止至本博客发表时，BZOJ1607题面有误，正确题面请到洛谷2926查看）

分析：