Alice的面试

Description

Alice参加面试时遇到了一个难题：给定一个正整数N，判断等式是否成立（i>0）（a不等于b）

Input

输入包含正整数N （0<N<1000000）

Output

若等式成立，请输出a b（中间有空格）；否则输出“NO”（不包含引号）。此题有多种情况，只计算a小的那组情况

Sample Input

1

Sample Output

NO

题解：

分析：
输入一个正整数N（1<=N<=1000000)，判断是否存在a到b（a!=b)之间连续求和是否等于N。
显而易见，a到b求和为等差数列求和，差值固定为1，由等差数列求和公式 ：

Sn=(a0+an)*n/2

（a0为首项，即本题的 a，an为尾项，即本题的 b,n则为项次）
可知:

N=(a+b)*(b-a+1)/2

由于区间连续求和，可知a<b<=500000。
因此直接遍历。

AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
    long long n;
    while(~scanf("%lld",&n))
    {
        long long i,j,b,x,flag=0;
        if(n<=2)  //n<2时无
        {
            cout<<"NO"<<endl;
            continue;
        }
        for(i=1; i<50000; i++)
        {
            for(j=i+1; j<=50000; j++)
            {
                if(n==((i+j)*(j-i+1)/2))
                {
                    cout<<i<<" "<<j<<endl;
                    flag=1;
                    break;
                }
                if(i>=n)
                {
                    flag=2;
                    break;
                }
                if(j>=n)
                    break;
            }
            if(flag)
                break;
        }
        if(flag!=1)
            cout<<"NO"<<endl;
    }
    return 0;
}