TIOJ 1241 倍因道 Factor and Points [Sieve...?]

poao899    -4K    61MS    G++     0.44K     2009-11-19 17:11:34                              .

還是應該算Greedy(咦


Greedy檢查每個數適合當因數還是倍數

//************************

#include<stdio.h>
#include<algorithm>
int fac[2001];
int n,t,total;
main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		total=0;
		for(int i=0;i<2001;i++)
			fac[i]=0;
		for(int i=1;i<=n;i++){
			int m=n/i-1;
			if(m>fac[i])
				for(int j=i+i;j<=n;j+=i)
					fac[j]++;
			else total+=fac[i];
		}
		printf("%d\n",total);
	}
}