AOJ 2101 完全数

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2101

約数の和を求めるだけなんですが、単純に与えられた値nまで回して割りきれた数を記録すると入力データの上限が一億なのでTLEしてしまう。

#include <cstdio>
int main(){
	int n,r,i;
	while(scanf("%d",&n)&&n){
		/*-nで初期化。この後にするループでn/1=nの組み合わせが生じるのでそれ対策(※nを除く約数と指定されているため)*/
		r=-n;

		/*1から√nまでループをする。i*i≦nはi≦√nと同義　*/
		for(i=1;i*i<=n;i++){
			if(n%i==0){
				/*割った数と割った結果はどちらも約数なのでrに足している*/
				r+=i+n/i;
				/*割った数と結果が等しいと約数を二重に足していることになるので除算する*/
				if(i==n/i)r-=i;
			}
		}
		
		/*変な出力 気にしない*/
		printf("%s",n>r?"deficient number":n<r?"abundant number":"perfect number");
		
	}
}

普通にnまでループ回していたので2回くらいTLEした。1から√nまで割って、割りきれた数とその数で割った結果を全て記録すれば全ての約数が求まるというルールを忘れてました。

√100000000=10000なので10000回以内のループに収まる。平方根強い。

てか

『1億までのnが与えられる。辺の長さが自然数で面積がnになるような長方形のパターンの数を求めよ。また、取りうる全ての辺の長さの和が2nであれば○、2nより小さければ□、2nより大きければ△とする。』

この説明だと少し悪問だけど、こんな感じに全く別の問題で出された方が、性質は同じだけどちょっと正答率上がる気がする。

(完全数 = n自身を除いた約数の和がnと等しい = nを含めた約数の和が2nと等しい)

おまけ(175 Bytes)

main(n,r,i){for(;scanf("%d",&n)&&n;puts("t number")){r=-n;for(i=1;i*i<=n;i++)if(n%i==0){r+=i+n/i;if(i==n/i)r-=i;}printf("%s",n>r?"deficien":n<r?"abundan":"perfec");}exit(0);}