本文最后更新于:2020年4月11日 下午

题目简述

  • 输入$L,s$中三个边为$a,b,c$的三角形中有多少个满足以下条件:

  • $a,b,c$是满足$a≤b≤c$且$\gcd(a,b,c)= 1$的自然数。

  • $a ^ 2 + b ^ 2 + s ^ 2 = c ^ 2$

  • $a + b + c≤L$

题目分析

当$s = 0$时,($a,b,c$)代表直角三角形的三个边。
通过将列向量($a,b,c$)依次乘以以下三个矩阵,可以枚举所有勾股数。

[+1 -2 +2] [+1 +2 +2] [-1 +2 +2] 
[+2 -1 -2] [+2 +1 +2] [-2 +1 +2]
[+2 -2 +3] [+2 +2 +3] [-2 +2 +3]

上面的矩阵保持$c ^ 2-a ^ 2-b ^ 2$的值。

因此,即使上述矩阵应用于($a,b,c$)使得$a ^ 2 + b ^ 2 + s ^ 2 = c ^ 2$,即使它不是毕达哥拉斯数,$a ^ 2 +$可以列出满足$b ^ 2 + s ^ 2 = c ^ 2$的($a,b,c$)。

根据上面的方程式和三角形的条件,$a <2s$,($cb$)($c + b$)$= a ^ 2 + s ^ 2$。

因此,让我们在该范围内四舍五入,然后找到$b$和$c$。
之后,以DFS方式将上述三种类型的矩阵相乘,并且列出满足条件的($a,b,c$)。

$Code$

ll L,S;
ll ret;
set<int> SS[50501];

void dfs(int a,int b,int c,int step) {
	if(a+b+c>L) return;
	
	int x=__gcd(a,b);
	if(x>1 && __gcd(x,c)>1) return;
	
	if(a<=10100) {
		if(SS[a].count(b)) return;
		SS[a].insert(b);
	}
	if(a && a+b>c) ret++;
	
	dfs(1*a-2*b+2*c,2*a-1*b+2*c,2*a-2*b+3*c,step+1);
	if(a<b) dfs(-2*a+1*b+2*c,-1*a+2*b+2*c,-2*a+2*b+3*c,step+1);
	dfs(2*a+1*b+2*c,1*a+2*b+2*c,2*a+2*b+3*c,step+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	int a,b,c,g;
	cin>>L>>S;
	
	for(a=0;a<=2*S;a++) {
		ll d = a*a+S*S;
		for(ll cb=1;cb*cb<d;cb++) if(d % cb==0) {
			ll cb2=d/cb;
			if((cb+cb2)%2) continue;
			c = (cb+cb2)/2;
			b = (cb2-cb)/2;
			dfs(min(a,b),max(a,b),c,0);
		}
	}
	
	cout<<ret<<endl;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT865 【お風呂は気持ちいい】 上一篇
题解 AT2027 【天下一プログラマーコンテスト1999】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。