HDU 1215(七夕节)

spoiler posted @ 2011年4月17日 03:34 in 未分类 , 1148 阅读

题目大意:您的编号N的因子和就是您的另一半的编号!数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

题目分析:其实是水题!一开始想复杂了,后来想想看,我们只要找i :1->sqrt(N)然后用通过N/i 找到比sqrt(N)大的满足要求的因子!

这样最坏情况下也才500000*3000最多!还是不会超时的

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int solve(int x){
	int i,j,sum=0;
	double tempt=sqrt(x);
	for(i=2;i<=tempt;i++){
		if(x%i==0){
			sum+=i;
			int t=x/i;
			if(t!=i){
				sum+=t;	
                          //是在里面判断比sqrt(N)大的因子合法与否!
			}
		}
	}
	sum+=1;
	return sum;
}
int main(){
	int cas,t,ans;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&t);
		ans=solve(t);
		printf("%d\n",ans);
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter