D. Pythagorean Triples 题解

思路

由勾股定理和题目中的要求对应的两个方程可以得到一个等式：

c方-b方 = c + b

在题目要求下可以知道 c = b+1

拿这个式子去打表，找符合这个式子的直角三角形

import math
for i in range(1,1001):a = ib = i+1a = a*ab = b*bc = b-ad = math.sqrt(c)d = int(d)if d*d == c:print(f"{d} {i} {i+1}")
# 3 4 5
# 5 12 13
# 7 24 25
# 9 40 41
# 11 60 61
# 13 84 85
# 15 112 113
# 17 144 145
# 19 180 181
# 21 220 221
# 23 264 265
# 25 312 313
# 27 364 365
# 29 420 421
# 31 480 481
# 33 544 545
# 35 612 613
# 37 684 685
# 39 760 761
# 41 840 841
# 43 924 925

从打表结果可以发现，符合要求的三角形满足：

1、a是奇数，且除了1以外的每个正奇数都有对应的符合要求的直角三角形

2、c = b+1

3、b = (a*a-1)/2

因为题目中是求1-n范围中有多少个符合要求的三角形，所以从n开始倒着找，找到的第一个符合要求的三角形的  a/2  即为答案

AC代码 

为什么从python变成c艹了，因为用python交了超时

#include<bits/stdc++.h>
using namespace std;#define int long longint n,t,z,m;void solve(){cin>>n;if(n<5){cout<<0<<'\n';return ;}for(int i=n;i>0;--i){z = (i-1)*2+1;t = sqrt(z);if(t*t==z && t&1){cout<<(t>>1)<<'\n';return ;}}
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int _=1;cin>>_;while(_--){solve();}    return 0;
}