洛谷 CF707C Pythagorean Triples の 题解

发布时间 2023-09-13 11:37:23作者: NFGase

这道题是一道数论题,不可用暴力通过,因为输入范围极大,基本上循环是不能在这道题上使用的了。

前面大佬们讲的我听不懂,于是在教练的帮助下,我利用题面给出的多组样例找到了规律。

在此之前,我们先设输入的数为 $n$ 。

$n$ 分三种情况。

  • $n$ 是奇数;
  • $n$ 是偶数;
  • $n$ 小于等于 $2$;

首先咱们必须把 $n$ 小于等于 $2$ 的这种情况清除掉,众所周知,这种数是不可能存在解的,于是直接输出 -1 并结束程序即可。

之后咱们再看 $n$ 是奇数这种情况,不难发现,输出的第一个数等于 $n ^ {2} \div 2$,而第二个数则是 $(n ^ {2} \div 2) + 1$ 。

$n$ 若是偶数则将其除以 $2$ 转化为奇数,之后输出时乘以 $2$ 即可。

代码如下

#include <iostream>
using namespace std;
long long n;
int main(){
   cin >> n;
   if(n <= 2){
       cout << -1;
       return 0;
   }
   if(n % 2 != 0) cout << ((n * n) / 2) << " " << ((n * n) / 2) + 1;
   else{
       n /= 2;
       cout << (n * n) - 1 << " " << (n * n) + 1;
   }
   return 0;
}

评测结果