BNUOJ 1777

题目链接：http://acm.cist.bnu.edu.cn/contest/contest_problem_show.php?cpid=1777

C: 约数的个数

Time Limit: 6000 ms Case Time Limit: 2000 ms Memory Limit: 65535 KB
Submit: 158 Accepted: 24

Description

如果一个整数a能够整除整数b，那么a叫做b的约数。
现在有N(1 <= N <= 100,000)个整数，对于其中的每一个数，请找出它在其余N - 1个整数中有多少个约数。

Input

输入数据的第一行是一个整数N，以下N行每行有一个正整数，每个都不会超过1,000,000。

Output

按输入顺序输出每个整数在其余N - 1个整数中的约数的个数，每个整数一行，总共输出N行。

Sample Input

5
2
1
2
3
4

Sample Output

2
0
2
1
3

先开始把题目看错了，以为是直接求n的约数个数，结果连样例都过不了。。。脸丢大了

这个题，题目时限很宽松，给了我们6秒，可谓时间充裕。

但是仍然不能采取O(n*m)的算法，因为这里n是10w，m是100w直接暴力肯定要超时。

我的方法是先开一个数组来记录每一个值出现的次数。

然后再通过枚举m的约数（这里只需要枚举到sqrt(m)就行了）来计算总次数。

这里时间复杂度变成了O(n*sqrt(m))在最坏的情况下，我们需要计算10w*sqrt(100w)=10w*1000=10^8

但是题目时限是6s而且这个已经是最坏的情况，所以是可以AC的

我的代码：

#include<stdio.h>
#include<string.h>

int hash[1000005];
int a[100005];

int main()
{
	int i,j,n,ans;
	while(scanf("%d",&n)!=EOF)
	{
		memset(hash,0,sizeof(hash));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			hash[a[i]]++;
		}
		for(i=1;i<=n;i++)
		{
			ans=0;
			for(j=1;j*j<=a[i];j++)
			{
				if(a[i]%j==0&&j*j!=a[i])
				{
					ans=ans+hash[j];
					ans=ans+hash[a[i]/j];
				}
				if(j*j==a[i])
					ans=ans+hash[j];
			}
			if(ans)
				printf("%d\n",ans-1);
			else
				printf("%d\n",ans);
		}
	}
	return 0;
}