站外题求条

rt，楼主使用高妙算法被神秘测评机轻松击落，仅拿到10pts高分

题面如下：

ACMer中的大神们都很喜欢数学。现在阜阳师范ACM集训队中也有一位成长中的小牛正在研究数学呢。刚好他就遇到一个有趣的问题。比如，如果一个直角三角形的周长是120的话，那么他的三条边可以是20，48，52，或者24，45，51，还有30，40，50，有三种不同的解。现在他想知道如果给定一个直角三角形的周长，那么这个周长最多能有多少解呢？输入格式:

CPP

第一行一个T表示T组测试数据。1<=T<=10000 


每组测试数据占一行仅含一个整数A。0<=A<=100000

输出格式:

CPP

根据每组测试数据请求出以整数A为周长的直角三角形的个数。（边长都为整数的直角三角形且周长为整数A）

限制:

空间限制：32MByte 时间限制：1秒

CPP

我的代码：
#include <bits/stdc++.h>
using namespace std;
int cnt;
int a[70010],b[70100],c[70100];
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int main() {
	int q;
	cin>>q;
	while(q--) {
		int t;
		cin>>t;
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		cnt=0;
		for(int i=1; i*i<=t; i++) {
			if(t%i==0) {
				int k=i;
				for(int j=0; j*j*4<t/i; j++) {
					if((2*t)%k==0) {
						int m=j;
						int p=j*j+2*t/k;
						if((int)(sqrt(p))*(int)(sqrt(p))==p&&sqrt(p)-m>0&&((int)(sqrt(p))-m)%2==0) {
							int n=((int)(sqrt(p))-m)/2;
							int t1=2*k*m*n;
							int t2=k*(n*n-m*m);
							int t3=k*(n*n+m*m);
							if(a[t1]==0&&b[t2]==0&&c[t3]==0) {
								cnt++;
							}
							a[t1]=1;
							b[t2]=1;
							c[t3]=1;
						}
					}
				}
			}
		}
		cout<<cnt<<endl;
	}

	return 0;
}

思路是这样的先用勾股数生成式子算出式子里面的两个参数，再根据n>m定下范围最后去重，算的部分没错，时间貌似不会超，去重那部分空间时间都超了，有没有办法小清新地做掉这道题

讨论操作

回复

相关推荐

站外题求条