三角形 - 枚举

（我真是个zz） 题目大意： 给你n条边，长度都是整数并且不超过A，问有多少选三条边的方案，能够成直角三角形。A<=1e5,n<=1e6。 题解：直接枚举…… Mysolution：根据数论知识，$x^2+y^2=z^2$通解是： $x=t(a^2-b^2),y=t(2ab),z=t(a^2+b^2)$ 那么枚举y，枚举t，枚举a，得到b，算出x和z即可。复杂度是所有数字的因数的因数和，大概在8e5左右。注意去重。

#include<bits/stdc++.h> #define gc getchar() #define rep(i,a,b) for(int i=a;i<=b;i++) #define Rep(i,v) rep(i,0,(int)v.size()-1) #define lint long long #define mod 998244353 #define db long double #define pb push_back #define mp make_pair #define fir first #define sec second #define debug(x) cerr<<#x<<"="<<x #define sp <<" " #define ln <<endl using namespace std; typedef pair<int,int> pii; typedef set<int>::iterator sit; inline int inn() { int x,ch;while((ch=gc)<'0'||ch>'9'); x=ch^'0';while((ch=gc)>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x; } unordered_set<lint> s;const lint BAS=10000000ll; const int N=100010;int cnt[N];vector<int> d[N]; int main() { int n=inn(),A=inn();lint ans=0;rep(i,1,n) cnt[inn()]++; rep(i,1,A) for(int j=i;j<=A;j+=i) d[j].pb(i); for(int y=2;y<=A;y+=2) if(cnt[y]) { Rep(tc,d[y/2]) { int t=d[y/2][tc],ab=y/2/t; Rep(ac,d[ab]) { int a=d[ab][ac],b=ab/a;if(a<=b) continue; lint x=(lint)t*(a*a-b*b),z=(lint)t*(a*a+b*b); if(z>A||!cnt[x]||!cnt[z]) continue; if(s.count(max(x,(lint)y)*BAS+min(x,(lint)y))) continue; s.insert(max(x,(lint)y)*BAS+min(x,(lint)y)); ans+=(lint)cnt[x]*cnt[z]%mod*cnt[y]%mod; } } } return !printf("%lld\n",ans%mod); }