/*
* 程序的版权和版本声明部分:
* Copyright (c) 2014,郑州大学SIAS国际学院
* 作 者: 王 杰
* 完成日期:2014 年 2 月 15 日
*
* 对任务及求解方法的描述部分:
* 输入描述: 略或见注释、总结
* 问题描述: 略或见注释、总结
* 程序输出: 略或见注释、总结
* 问题分析: 略或见注释、总结
* 算法设计: 略或见注释、总结
*/
//超时。....
#include<stdio.h>
int main()
{
int t;
int n,j;
register int i;
scanf("%d",&t);
while(t--){
j=0;
scanf("%d",&n);
for(i=1;i<n;i++){
if(n%i==0)
j+=i;
}
printf("%d\n",j);
}
return 0;
}
运行结果:正确但超时!
改进版:
/* * 程序的版权和版本声明部分: * Copyright (c) 2014,郑州大学SIAS国际学院 * 作 者: 王 杰 * 完成日期:2014 年 2 月 15 日 * * 对任务及求解方法的描述部分: * 输入描述: 略或见注释、总结 * 问题描述: 略或见注释、总结 * 程序输出: 略或见注释、总结 * 问题分析: 略或见注释、总结 * 算法设计: 略或见注释、总结 */ #include<stdio.h> int biao[500001]={0}; int main() { int t,n,i,j; //打表 for(i=2;i<=500001;i++){ for(j=2*i;j<=500001;j+=i){ biao[j]+=i; } } scanf("%d",&t); while(t--){ scanf("%d",&n); if(n==1) printf("0\n"); else printf("%d\n",biao[n]+1); } return 0; }
运行结果:
总结:打表,提高效率。 何为打表?就是把所有的结果事先做成一个正确的表