咖啡


私信TA

用户名:Tianxn

访问量:88155

签 名:

十年OI一场空,不开LL见祖宗。

等  级
排  名 7
经  验 20311
参赛次数 9
文章发表 197
年  龄 22
在职情况 学生
学  校 西安航空学院
专  业 软件工程

  自我简介:

解题思路:
1、暴力

暴力方法就是每次枚举起点和终点,统计起点和终点直接的和是否满足即可,代码如下:

#include <iostream>
using namespace std;
int sum, m;

int main()
{
	while (cin >> m) {
		for (int i = 1, j; 2 * i < m; ++i) {
			sum = 0;
			for (j = i; j < m; ++j) {
				sum += j;
				if (sum >= m) break;
			}
			if (sum == m) cout << i << " " << j << endl;
		}
		cout << endl;
	}
	return 0;
}

2、前缀和

从暴力的基础上修改,暴力的内层循环使用前缀和简化

#include<cstdio>
using namespace std;

int s[2000005], m;

int main()
{
	while(~scanf("%d", &m)) {
		for(int i = 1; i <= m; i++) s[i] = s[i - 1] + i;
		for(int i = 1; i < m; i++)
			for(int j = i + 1; s[j] - s[i - 1] <= m; j++)
				if(s[j] - s[i - 1] == m)
					printf("%d %d\n", i, j);
		puts("");
	}
	return 0;
}

3、数学

设首项为L,末项为R,那么sum(L,R)=(L+R)(R-L+1)/2=M

即(L+R)(R-L+1)=2M

可以把2M分解成两个数之积,假设分成了两个数i,j,且i<j 

可以列一个二元一次方程组R-L+1=i,L+R=j

解得L=(j-i+1)/2, R=(i+j-1)/2

当i,j一奇一偶时,L,R才有自然数解.

不过有一种特殊情况,就是L=R的情况,这种情况是不允许的

即(j-i+1)/2≠(i+j-1)/2,解得i≠1 

#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
	int m;
	while (~scanf("%d", &m)) {
		for(int i = sqrt(2 * m); i>1; i--) //枚举i(注意是i>1而不是i>=1)
			if(2 * m % i == 0 && (i + 2*m/i) % 2) { //如果j是整数而且与i一奇一偶
				int j = 2 * m / i;
				printf("%d %d\n", (j - i + 1) / 2, (i + j - 1) / 2);//输出答案
			}
		puts("");
	}
	return 0;
}


 

0.0分

3 人评分

  评论区

德国人
2021-10-07 14:14:04 | |
前缀+二分过测试点耗时160+ms,而暴力求解却只需耗时50+ms,搞不明白为什么。
2021-04-22 20:18:37 | |
  • «
  • 1
  • »