【题目链接】

ybt 1621：轻拍牛头
洛谷 P2926 [USACO08DEC] Patting Heads S

【题目考点】

1. 数论：约数

【解题思路】

有n个数，对于其中每个数，问这n个数中有几个数是它的约数。
基本想法是枚举，对于每个数$a_i$，遍历n个数，计数看有多少数字是$a_i$的约数。时间复杂度为$O(n^2)$，而本题$n$最大为$10^5$，$n^2=10^{10}>10^8$，不可行。
可以反过来找所有$a_i$的约数，看每个$a_i$的约数在这n个数中有几个，将所有$a_i$约数在这n个数中的个数进行加和即可。
将输入的n个数保存在a数组，a[i]表示第i个数。
设计数数组c，c[i]表示输入的n个数中，数值i出现的次数。
遍历a数组，对于第i个数a[i]，设ct表示a[i]的约数在这n个数中个数。
枚举找出a[i]的每个约数j，加和变量ct增加该约数在输入的n个数中出现的次数c[j]。
找$a_i$约数的方法为，j从1循环到$\lfloor \sqrt{a_i}\rfloor -1$，如果j是$a_i$的约数，则$\frac{a_i}{j}$也是$a_i$的约数。而后看$\sqrt{a_i}$是否是$a_i$的约数。
由于a[i]在这n个数中的约数还包括自己，所以实际约数的个数需要减1。每次循环最后输出ct-1。
统计每个数字的约数的时间复杂度为$O(\sqrt{m})$，m为数值范围，最大为$10^6$，需要循环n次，总体时间复杂度为$O(n\sqrt{m})$，n最大为$10^5$。
$n\sqrt{m}$最大为$10^5\sqrt{10^6}=10^8$，实际不是每个数字都是$10^6$，因此可以接受。

由于序列中可能有重复数字，可以设数组ans，ans[i]记录数值i在序列中的约数个数（不包括自己），如果已经求出过ans[i]，可以直接查询，不需要再次求解。

【题解代码】

解法1：求约数

#include<bits/stdc++.h>
using namespace std;
int c[1000005], a[100005];//c[i]：数字i出现的个数 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, j, ct;
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		c[a[i]]++;
	}
	for(int i = 1; i <= n; ++i)
	{
		ct = 0;//a[1]~a[n]中a[i]的约数个数。 
		for(j = 1; j*j < a[i]; ++j) if(a[i]%j == 0) //如果j是a[i]的约数		
			ct += c[j]+c[a[i]/j];//那么j和a[i]/j都是a[i]的约数，增加二者出现的数量 
		if(j*j == a[i])//如果j==sqrt(a[i])，j也是a[i]的约数 
			ct += c[j];
		cout << ct-1 << '\n'; //在这过程中计算了自己，减1 
	}
	return 0;
}

解法2：求约数 使用ans数组记录结果

#include<bits/stdc++.h>
using namespace std;
int c[1000005], a[100005], ans[1000005]; 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, j, ct;
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		c[a[i]]++;//c[i]：数字i出现的个数
	}
	memset(ans, -1, sizeof(ans));//ans[i]：数值i在序列中的约数个数-1，初值都设为-1 
	for(int i = 1; i <= n; ++i)
	{
		if(ans[a[i]] > -1)
			cout << ans[a[i]] << '\n';
		else
		{ 
			for(j = 1; j*j < a[i]; ++j) if(a[i]%j == 0) //如果j是a[i]的约数		
				ans[a[i]] += c[j]+c[a[i]/j];//那么j和a[i]/j都是a[i]的约数，增加二者出现的数量 
			if(j*j == a[i])//如果j==sqrt(a[i])，j也是a[i]的约数 
				ans[a[i]] += c[j];
			cout << ans[a[i]]<< '\n'; //在统计过程中需要减掉自己，ans[a[i]]初值为-1，就不用再减了 
		} 
	}
	return 0;
}