期末考试YTU4035: Shmily(数学,等差数列)-526互联

考试的时候看到这道题一眼前缀和,但是想了想要枚举每个区间是不是复杂度有点高,还是交上去了

不出意外的 $TLE$ 了,想了十来分钟还是没想到怎么优化,考完问了一下大佬,原来用等差数列1ms就能过,听说双指针0ms(蒟蒻的我呜呜)

众所周知等差数列的前 $N$ 项和是 $S$ =a₁*n+(n*(n-1))/2,用这个公式来求就可以了

//  ((n-1)*n)/2+n*x==y
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long  m,n,a[N],t,num;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cout<<"CASE"<<++num<<endl;
        cin>>n;
        int cnt=1;
        set<pair<int,int>>a;
        while(cnt++){
            int s=n-(cnt*(cnt-1)/2);
            if(s<0) break;
            if(s%cnt==0){
                int m=s/cnt;
                if(m!=n) a.insert({m,m+cnt-1});
            }
        }
        for(auto i:a) cout<<i.first<<" "<<i.second<<endl;
    }
    return 0;
}