又是双指针问题

lsmCC

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. typedef long long ll;
   
4. ll m;
   
5. int main()
   
6. {
   
7.     cin>>m;
   
8.     int i=1,j=1,sum=1;
   
9.     while(i<=m/2)
   
10.     {
    
11.         j++;
    
12.         sum+=j;
    
13.    
    
14.     if(sum>=m)
    
15.     {
    
16.         if(sum==m)cout<<i<<j<<endl;
    
17.         sum-=i;
    
18.         i++;
    
19.     }
    
20.     }
    
21. 
    
22. }

复制代码

为什么会没有输出呢
题目链接：https://www.luogu.com.cn/problem/P1147

FishC_GPT

在你的代码中，你将`=`号误写成了`==`号，在`while`循环的条件判断中应该改为`while(i == m)`。另外，你没有对`sum`进行更新操作，所以无法退出循环。在每次循环结束后，你需要更新`sum`的值。以下是修正后的代码：

1. #include <iostream>
2. using namespace std;
3. typedef long long ll;
4. ll m;
6. int main()
7. {
8.     cin >> m;
10.     int i = 1, j = 1, sum = 1;
11.     while (i <= m)
12.     {
13.         if (sum == m)
14.             cout << i << " " << j << endl;
15.         
16.         if (sum <= m)
17.         {
18.             j++;
19.             sum += j;
20.         }
21.         else
22.         {
23.             sum -= i;
24.             i++;
25.         }
26.     }
28.     return 0;
29. }

复制代码

这段代码使用了双指针的思想来解决问题。其中，变量`i`代表当前的起始位置，变量`j`代表当前的结束位置，变量`sum`代表从`i`到`j`的连续整数的和。如果`sum`等于目标值`m`，则输出`i`和`j`。然后，根据`sum`与`m`的关系来移动`i`和`j`的位置，使得`sum`接近`m`。

希望能帮到你！
以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

tommyyu

你这种做法不一定能找到答案，可以用二元二次方程。
由题意得，x + (x+1) +... +y = m
而 x + (x+1) + ... + y = (1 + ... + y) - (1 + ... + (x-1))
                                 = (y+1)*y/2 - (x-1)*x/2
此时枚举 x 的值，有
(y+1)*y/2 - (x-1)*x/2 = m
(y+1)*y - (x-1)*x = 2*m
(y+1)*y = 2*m+(x-1)*x
此时就有一种快速计算y的方法，先算出右边的值，再直接开根号得到一个小数，此时将这个小数变为整数，即有可能是 y 的值，之后计算验证即可。

1. #include <iostream>
   
2. #include <cmath>
   
3. using namespace std;
   
4. int main()
   
5. {
   
6.         long long m, x, y; cin >> m;
   
7.         for(x=0; x<m; ++x) {
   
8.                 y = (long long)sqrt(2*m+(x-1)*x);
   
9.                 if(y*(y+1) - x*(x-1) == 2*m && x < y) cout << x << " " << y << endl;
   
10.         }
    
11.         return 0;
    
12. }

复制代码

ps: 我第一次试的时候没开 long long 就爆了