题解 | #D#

注意到题目要求正整数解，考虑十字相乘

(x-a)(x-b)=0,即x^2-(a+b)x+ab=0

此时p=a+b,q=ab,问题转化为k能否分解为两个自然数a,b满足a+b+ab=k

枚举a得b=(k-a)/(1+a),判断此时的a,b是否满足条件即可

注意到a只需要枚举到sqrt(k),时间复杂度即O(sqrt(k))

#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
int k;
signed main() {
    cin>>k;
    if(k==1){
        cout<<-1;return 0;
    }
    if(k%2!=0){
        cout<<k/2+1<<" "<<k/2;
        return 0;
    }
    else{
        for(int i=1;i<=k/i;i++){
            int j=(k-i)/(1+i);
            if(i+j+i*j==k){
                cout<<i+j<<' '<<i*j;
                return 0;
            }
        }
    }
    cout<<-1;
	return 0;
}