HDU 1215 七夕节数学题~

http://acm.hdu.edu.cn/showproblem.php?pid=1215

题目大意：

找对象的题。。。汗。。将你的编号（唯一）的所有因子加起来，所得到的的另一个编号的主人就是你的另一半。给出你的编号，要求找到你的对象的编号。

一开始直接模拟TLE。

然后后来看到别人是这么做的：

#include<cstdio>

#include<string>

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n;

		scanf("%d",&n);

		int cur=2;

		int ans=1;

		for(int i=2;(i>>1)<=n;i++)    //将问题规模减半

		{

			if(n%i==0)

			{

				if(n/i > i)				//如果把不等于i,那么说明i和n/i都是因子

					ans+=n/i+i;

				else if(n/i==i)			//等于i就一个因子

					ans+=i;

				else                   //如果n/i<i说明因子算完了。。

					break;

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

后来采用类似筛选素数的方法，打表。

我们先将2的倍数的都+上2.。。3的倍数都加上3、。。。。

要注意的是如果n==1的时候答案为0.

#include<cstdio>

const int MAXN=500000+1;

const int N=250000;

int ans[MAXN]={0};

int main()

{

	for(int i=2;i<MAXN;i++)

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

			ans[j]+=i;

	ans[1]=-1;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n;

		scanf("%d",&n);

		printf("%d\n",ans[n]+1);

	}

	return 0;

}

巴特西

HDU 1215 七夕节数学题~

最新文章

热门文章

巴特西

HDU 1215 七夕节 数学题~

最新文章

热门文章

HDU 1215 七夕节数学题~