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;
}