51nod 1165 整边直角三角形的数量

直角三角形，三条边的长度都是整数。给出周长N，求符合条件的三角形数量。

例如：N = 120，共有3种不同的满足条件的直角3角行。分别是：{20,48,52}, {24,45,51}, {30,40,50}。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000)

第2 - T + 1行：每行1个数N(12 <= N <= 10^7)。

Output

输出共T行，每行1个对应的数量。

Input示例

Output示例

3

0

题意：问有多少种直角三角形的周长恰好为n
分析：
假设a<b<c
a+b+c=n
a^2+b^2=c^2
c = sqrt(a^2+b^2)
c=n-(a+b)
c^2 = a^2+b^2 = (n-(a+b))^2
a^2+b^2 = n^2 - 2*(a+b)*n + a^2 + b^2 + 2*a*b
2*(a+b)*n = n^2 + 2*a*b
2*n*b - 2*a*b = n^2 - 2*m*a
b = (n^2 - 2*n*a) / (2*n - 2*a)
设 t = n-a
b = (2*(n^2 - n*a) - n^2)  /   2*(n-a)
  = n - n^2/(2*t)

因为 t = n-a, a < b < c, a+b > c, c < n/2
所以

n-t = a < b = n- n^2/(2*t)
n^2/(2*t) < t
n^2 < 2*t^2
2*t > sqrt(2)*n

t < n

所以 sqrt(2)*n < 2*t < 2*n

所以，只需要找出n的所有因数，把它们个数*2，就是L^2因数的个数
然后枚举每个因数多少个（注意，2*t显然是2的倍数），记一下在那个范围里面的个数，即为答案

下面上代码

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <ctime>

 using namespace std;

 typedef long long LL;

 typedef double DB;

 #define For(i, s, t) for(int i = (s); i <= (t); i++)

 #define Ford(i, s, t) for(int i = (s); i >= (t); i--)

 #define Rep(i, t) for(int i = (0); i < (t); i++)

 #define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)

 #define rep(i, x, t) for(int i = (x); i < (t); i++)

 #define MIT (2147483647)

 #define INF (1000000001)

 #define MLL (1000000000000000001LL)

 #define sz(x) ((int) (x).size())

 #define clr(x, y) memset(x, y, sizeof(x))

 #define puf push_front

 #define pub push_back

 #define pof pop_front

 #define pob pop_back

 #define ft first

 #define sd second

 #define mk make_pair

 inline void SetIO(string Name) {

     string Input = Name+".in",

     Output = Name+".out";

     freopen(Input.c_str(), "r", stdin),

     freopen(Output.c_str(), "w", stdout);

 }

 const int N = , M = ;

 int Prime[M], Tot;

 bool Visit[N];

 int n;

 int Factor[M], Num[M], Len;

 int Left, Right, Answer[N], Ans;

 inline void GetPrime() {

     For(i, , N-) {

         if(!Visit[i]) Prime[++Tot] = i;

         For(j, , Tot) {

             if(i*Prime[j] >= N) break;

             Visit[i*Prime[j]] = ;

             if(!(i%Prime[j])) break;

         }

     }

 }

 inline void Solve();

 inline void Input() {

     GetPrime();

     int TestNumber;

     scanf("%d", &TestNumber);

     while(TestNumber--) {

         scanf("%d", &n);

         Solve();

     }

 }

 inline void GetFactor(int x) {

     For(i, , Tot) {

         if(x ==  || Prime[i] > x) break;

         if(!(x%Prime[i])) {

             Len++;

             Factor[Len] = Prime[i], Num[Len] = ;

             while(!(x%Prime[i])) x /= Prime[i], Num[Len]++;

         }

     }

     if(x > ) {

         Len++;

         Factor[Len] = x, Num[Len] = ;

     }

 }

 LL Temp;

 inline void Search(int x, int Val) {

     if(Left < Val && Val < Right && !(Val%)) Answer[++Ans] = Val;

     if(x > Len || Val >= Right) return;

     int Cnt = ;

     For(i, , Num[x]) {

         Search(x+, Val*Cnt);

         if(Val*Cnt >= Right/Factor[x]) break;

         Cnt *= Factor[x];

     }

 }

 inline void Solve() {

     if(n&) {

         puts("");

         return;

     }

     Len = ;

     GetFactor(n);

     For(i, , Len) Num[i] <<= ;

     Ans = ;

     Left = n*sqrt(), Right = *n;

     Search(, );

     sort(Answer+, Answer++Ans);

     int p = ;

     For(i, , Ans)

         if(Answer[p] != Answer[i]) Answer[++p] = Answer[i];

     /*For(i, 1, p) {

         int b = n-n*n/Answer[i];

         int a = n-Answer[i]/2;

         int c = n-a-b;

         printf("%d %d %d %d\n", Answer[i], a, b, c);

     }*/

     printf("%d\n", p);

 }

 int main() {

     #ifndef ONLINE_JUDGE

     SetIO("");

     #endif

     Input();

     //printf("%d\n", Tot);

     //Solve();

     return ;

 }