POJ2140

由一道简单数学题引发的思考

所有的做法和注释和总结都在代码上了

这个题很有意思，不同的方法实现难度和AC时间也不一样的

int n;

int bruteforce(){
	//完全暴力的做法，从1开始作为起点，终点走到走不动为止
	//依次枚举起点和中间值，计算答案 
	int i,j,count=0,sum;
	for(i=1;i<=n;i++){
		sum=0;
		for(j=i;j<=n;j++){
			sum+=j;
			if (sum==n) count++;
			else if (sum>n) break;
		}
	}
	return count;
}

int formula(){
	//利用数学公式
	//S=(A1+Ak)*k/2
	//由于是连续的Ak=A1+(k-1)，故k和A1+Ak必然是一奇一偶
	//所以可以通过枚举k
	//计算出首项A1是否符合要求
	int count=0;
	int k=int(sqrt(2.0*n+0.5));
	for(int i=1;i<=k;i++){
		if (2*n%i==0&&((i&1)||(2*n/i)&1)){
			int a1=2*n/i-i+1;
			if (a1>=0) count++;
		}
	}
	return count;
}

int conclusion(){
	//假设a,a+1,a+2...a+k 
	//一组符合的答案
	//有 (k+1)a+0.5*k*(k＋1)=n成立 划成 (a + 0.5*k)(k+1)=n
	//观察等式发现必须满足 1. 0.5*k为整数. 所以k是偶数
	//2. (k+1) 为n的因数，并且 (k+1) 为奇数
	//所以综上 n有多少个奇因数，就是本题的答案
	//------来自于poj discuss Ly86.
	//当然，暴力方法可以改进到根号，注意49=7*7这种特殊情况特判 
	int count=0;
	for(int i=1;i<=n;i+=2)
		if (n%i==0) count++;
	return count;
}

int main(){
	//freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		//printf("%d\n",bruteforce());
		//printf("%d\n",formula());
		//printf("%d\n",conclusion());
	}
	return 0;
}