PE的这道题还挺有趣的。

数据不大,首先说一个手算的方法。
使用如下定理(从我原来的博客找来的):


由于所有勾股数都是这个三元组的倍数,所以有

又由于,并且s为奇数,所以s=5或s=25(125太大了)
当s=5时,由于t<s并且t为奇数,所以t=1或t=3,所以s(s+t)=30(舍)或s(s+t)=40
因为,so,ok~
所以abc=375·200·425=31875000
看看s=25,此时d(s+t)=40,只能取d=1,得t=15,不满足gcd(s,t)=1,舍之。

但是若a+b+c=sum很大,有没有一个通用的解法呢?

首先在<的范围内枚举sum的奇因子q。(分解sum再dfs可求得全部因子)
再枚举的偶因子q',注意要满足q<q'<2q,并且gcd(q,q'-q)=1
若枚举出来了就相当于求出来了。
复杂度

Comments

comments powered by Disqus