Portal --> who knows qwq

Description

　　给你\(n\)条边，长度都不超过\(A\)，问有多少种选边的方案满足这三条边能构成一个直角三角形

　　数据范围：\(1<=n<=10^6,1<=A<=10^5\)

　　

Solution

　　我的小学数学可能白学了qwq

　　

　　直觉是。。直接枚举勾股数但是这个东西要怎么枚举呢。。。

　　有两种方法：

　　第一种是对于所有的满足\(gcd(x,y,z)=1\)且\(x^2+y^2=z^2\)的三元组，它的解可以写成：

\[ \begin{cases} x=t(a^2-b^2)\\ y=2tab\\ z=t(a^2+b^2) \end{cases} \]

　　所以我们枚举这个\(a\)和\(b\)就好了，然后倍数跳上去。。

​ 　　

​　　第二种方法是如果说你不知道上面的这个结论，那么可以直接简单处理一下式子：

\[ \begin{aligned} x^2+y^2&=z^2\\ x^2&=z^2-y^2\\ &=(z-y)(z+y) \end{aligned} \]

　　所以我们可以枚举\(x\)，然后枚举\(x^2\)的因数就好了qwq

　　

​　　mark：主要是mark一下上面那个勾股数的结论qwq

　　

​　　第一种方法的代码大概长这个样子

#include
    
     #include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;const int N=1e6+10,MOD=998244353;int a[N];int cnt[N];int n,m,ans;int mul(int x,int y){return 1LL*x*y%MOD;}int plu(int x,int y){return (1LL*x+y)%MOD;}int gcd(int x,int y){return y?gcd(y,x%y):x;}int main(){#ifndef ONLINE_JUDGE    freopen("a.in","r",stdin);#endif    ll x,y,z;    scanf("%d%d",&n,&m);    for (int i=1;i<=n;++i) scanf("%lld",&x),++cnt[x];    for (int i=1;i*i<=m;++i){        for (int j=1;j<=i;++j){            x=1LL*i*i-1LL*j*j;            y=1LL*2*i*j;            z=1LL*i*i+1LL*j*j;            if (z>m) continue;            if (gcd(x,gcd(y,z))>1) continue;            for (int x1=x,y1=y,z1=z;z1<=m;x1+=x,y1+=y,z1+=z)                ans=plu(ans,mul(cnt[x1],mul(cnt[y1],cnt[z1])));        }    }    printf("%d\n",ans);}