codeforces707C

Pythagorean Triples

CodeForces - 707C

悉宇大大最近在学习三角形和勾股定理。很显然，你可以用三个边长为正数的线段去构造一个直角三角形，而这三个数被称作“勾股数”。

比如，（3,4,5），（5,12,13），（6,8,10）都是勾股数。

现在悉宇大大很好奇如果他能够确定直角三角形的某一条边，那么他能否找到另外两条边使得这三条边组成直角三角形。注意，他所确定的边可以是直角边也可以是斜边。

悉宇大大能够轻松的解决这个问题，你也可以吗？

Input

输入一个整数n(1 ≤ n ≤ 10⁹) ——直角三角形的一边的长度

Output

在一行里输出两个整数m，k(1 ≤ m, k ≤ 10¹⁸)，使得（n,m,k）为勾股数。

如果找不到任何勾股数包含n，那么输出-1。如果有多个答案，输出任意一个。

Examples

Input

Output

4 5

Input

Output

8 10

Input

Output

-1

Input

Output

144 145

Input

Output

2244 2245

sol：虽然是小学奥数，但还是蛮有趣的。
容易知道两个相邻的平方数的差就是按照3,5,7,9,11...这样排下去的，所以如果读入的数字不是2的倍数，那么就一直除到变成奇数，然后求出这个奇数的平方在前面那个序列中的位置，再把2乘回去就可以得到b,c
如果是2的幂次，观察3,4,5,按照这个比例构造另外两条边即可
Ps：方法应该挺多的，希望有大佬提供更好的qaq

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

int main()

{

    long long a,b,c,Base=;

    R(a);

    if(a<) return *puts("-1");

    while(a%==)

    {

        a/=;

        Base*=;

    }

    if(a>)

    {

        long long tmp=a*a;

        b=(tmp-)/;

        c=b+;

        b*=Base;

        c*=Base;

        W(b); Wl(c);

    }

    else

    {

        b=Base/*;

        c=Base/*;

        W(b); Wl(c);

    }

    return ;

}

/*

input

3

output

4 5

input

6

output

8 10

input

1

output

-1

input

17

output

144 145

input

67

output

2244 2245

*/

巴特西

codeforces707C

Pythagorean Triples

最新文章

热门文章