输出共T行，每行1个对应的数量。
解法1：所有本原直角三角形（即边为a、b、c，gcd（a，b，c）==1）可表示为两奇数s和t,s>t，gcd(s,t)==1, 边为st，(s*s-t*t)/2,(s*s+t*t)/2
反之，任意符合条件的s，t也可通过这样组成本原直角三角形
所以周长C= s*(s+t) ，对于C<=1e7,发现是s是sqrt级别的,可以s^2暴力求gcd即O（n*gcd复杂度），求出所有在数据范围内的本原直角三角形的周长
那么对于一个周长n，不同的直角三角形必定对应着不同的本原直角三角形，所以本原直角三角形周长必定是n的因子，枚举n的因子，然后统计答案
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<ll,int>pli;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e7+50;
const int mod = 1e9+7;
int mi[maxn],use[maxn],ggg[maxn];
void init(int c=maxn-10){
int cc=0;
for(int i=2; i<=c; ++i) {
if(!mi[i])use[++cc]=i,mi[i]=i;
int to=c/i;
for(int j=1; j<=cc and use[j]<=to; ++j) {
mi[use[j]*i]=use[j];
if(i%use[j]==0) break;
}
}
int u=sqrt(c);
for(int i=3;i<=u;i+=2){
int to=min(i-1,(c-i*i)/i);
for(int j=1;j<=to;j+=2){
if(__gcd(i,j)==1){
++ggg[i*(i+j)];
}
}
}
}
int f[520],cnt[520],cc;
int d[50000],gg;
void dfs(int cur,int now){
if(cur>cc){
d[++gg]=now;
}else{
for(int i=0;i<=cnt[cur];++i){
dfs(cur+1,now);
now*=f[cur];
}
}
}
int solve(int val,int ti){
int res=0;
int tmp=val;
cc=0;
while(tmp>1){
int v=mi[tmp];
f[++cc]=v;
cnt[cc]=0;
while(tmp%v==0){
++cnt[cc];
tmp/=v;
}
}
gg=0;
dfs(1,1);
for(int i=1;i<=gg;++i)
res+=ggg[d[i]];
return res;
}
int main() {
#ifdef local
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int T;cin>>T;
for(int i=1;i<=T;++i){
int val;cin>>val;
if(val&1)cout<<0<<"\n";
else cout<<solve(val,i)<<"\n";
}
return 0;
}
解法2：化式子
a*a+b*b = c*c
a+b+c = n
-> a+b+sqrt(a*a+b*b) = n
-> sqrt(a*a+b*b) = n-a-b
-> 两边平方并化简
-> n^2 - 2an = 2bn-2ab
-> b = (n^2-2an)/(2n-2a)
令f = n-a
则 b = n(2n-2a -n)/(2f) = n(2f - n)/(2f) = n- n^2/(2f)
则有2f | n^2
再看适用范围，有
0 < a < n/3
a < b (不会有等于，abc都是整数，a=b，c=sqrt(2)a × )
得到 n > f > 2n/3 -> 2n > 2f > 4n/3
n-f < n-n^2/(2f) -> 2f^2 > n^2 -> 2f > sqrt(2)n > 4n/3
所以 sqrt(2)n < 2t < 2n
当2t确定，a也确定了
所以在n^2的因子中找符合条件的数
#include<bits/stdc++.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<ll,int>pli;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e7+50;
const int mod = 1e9+7;
int mi[maxn],use[maxn],ggg[maxn];
inline int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
void init(int c=maxn-10){
int cc=0;
for(int i=2; i<=c; ++i) {
if(!mi[i])use[++cc]=i,mi[i]=i;
int to=c/i;
for(int j=1; j<=cc and use[j]<=to; ++j) {
mi[use[j]*i]=use[j];
if(i%use[j]==0) break;
}
}
// int u=sqrt(c);
// for(int i=3;i<=u;i+=2){
// int to=min(i-1,(c-i*i)/i);
// for(int j=1;j<=to;j+=2){
// if(gcd(i,j)==1){
// ++ggg[i*(i+j)];
// }
// }
// }
}
int f[520],cnt[520],cc;
ll d[50000],gg;
void dfs(int cur,ll now){
if(cur>cc){
d[++gg]=now;
}else{
for(int i=0;i<=cnt[cur];++i){
dfs(cur+1,now);
now*=f[cur];
}
}
}
int solve(int val,int ti){
int res=0;
int tmp=val;
cc=0;
while(tmp>1){
int v=mi[tmp];
f[++cc]=v;
cnt[cc]=0;
while(tmp%v==0){
++cnt[cc];
tmp/=v;
}
cnt[cc]<<=1;
}
gg=0;
dfs(1,1);
int l=sqrt(2)*val,r=val<<1;
for(int i=1;i<=gg;++i){
ll v=d[i];
if(v&1)continue;
if(v>l and v<r)++res;
}
return res;
}
int main() {
#ifdef local
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int T;cin>>T;
for(int i=1;i<=T;++i){
int val;cin>>val;
if(val&1)cout<<0<<"\n";
else cout<<solve(val,i)<<"\n";
}
return 0;
}
发现两种解法的运行速度差不多。。。
