P6695

看到这道题，原以为是暴力枚举，一看题目难度和数据范围就明白了，这是道数学题（其实我是看标签知道的）。

---

好了，言归正传。

solution

• 首先，区间长度等于 $1$ 是不可能的，具体可以看这篇题解。
• 当区间长度为 $2$ 时，由于相邻的两个数互质，所以左端点 $x$ 满足 $x(x+1)=m$ 此时化简方程得 $x^{2}+x-m=0$ 用二次方程求根公式取较大的 $\frac{-b+\sqrt{b^{2}-4ac}}{2a}$ 得 $x=\frac{-1+\sqrt{1+4m}}{2}$ 此时判断是否为整数即可。
• 当区间长度大于 $2$ 时，我可以暴力枚举左端点和右端点预处理存在 map 中。

code

#include<iostream>
#include<map>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
map<ll,pair<ll,ll> > s;
const ll INF=1e18;
ll pgcd(ll x,ll y){//gcd
    if(!y){
        return x;
    }
    return pgcd(y,x%y);
}
inline void pdy(ll m){
    ll x=sqrt(1+4*m);
    if(x*x==1+4*m){//判断
        x--;
        if(!(x&1)){//判断
            s[m]=make_pair(x/2,x/2+1);
        }
    }
    return;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll z;
    cin>>z;
    for(ll i=1;i<=2000000;i++){//预处理 i为左端点
        ll ans=i*(i+1);//求出前两个数的lcm
        for(ll j=i+2;;j++){
            ans/=pgcd(ans,j);//为了避免溢出，先除
            if(ans>INF/j){//是否超出最大值，等价于ans*j>INF,但是避免了溢出
                break;
            }
            ans*=j;
            if(!s.count(ans)){//如果先前没记录
                s[ans]=make_pair(i,j);
            }
        }
    }
    while(z--){
        ll m;
        cin>>m;
        //由于区间长的肯定左端点小，所以先看有没有区间较长的解
        if(s.count(m)){
            cout<<s[m].first<<" "<<s[m].second<<"\n";
        }else{
            //没有考虑长度为2时的解
            pdy(m);
            if(s.count(m)){
                cout<<s[m].first<<" "<<s[m].second<<"\n";
            }else{//如果还没有输出NIE
                cout<<"NIE\n";
            }
        }
    }
    cout<<flush;
    return 0;
}