[CF 707C]Pythagorean Triples

danihao123 posted @ 2016年8月21日 16:04 in 题解 with tags Codeforces 数学 构造 , 174 阅读
转载请注明出处:http://danihao123.is-programmer.com/

很好的数学题啊……

一看就应该想起来构造,对于[tex]n[/tex]为奇数的情况,我们可以假设[tex]n[/tex]为最小数。由此,可以构造出来[tex](n,(n^{2}-1)/2,(n^{2}-1)/2+1)[/tex]一组勾股数(具体证明自己证去)。

[tex]n[/tex]为偶数时呢?化成奇数做?不好,因为这样会出现对于[tex]n^{a} (a>1)[/tex]一类数会无能为力。偶数也可构造:[tex](n,(n/2)^{2}-1,(n/2)^{2}+1)[/tex]。

然后做就行了……

#include <iostream>
using namespace std;
int main(){
    long long n,temp;
    cin>>n;
    if(n<=2){
        cout<<-1<<endl;
        return 0;
    }
    if(1&n){
        temp=n*n-1;
        temp/=2;
        cout<<temp<<' '<<(temp+1)<<endl;
    }else{
        temp=n/2;
        cout<<temp*temp+1<<' '<<temp*temp-1<<endl;
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter