HNU_11722

    由于勾股数a,b,c可以表示成a=m^2-n^2，b=2*m*n，c=m^2+n^2，因此可以枚举n找到所有可能的互素的勾股数，然后去掉其中重复的解即可。

    这个题目还可以用一个剪枝，就是如果c%4 !=1的话一定无解。

#include
     
       #include
      
        #include
       
         #include
        
          #define MAXD 60000 int C, a[MAXD], b[MAXD], r[MAXD]; int gcd(int x, int y) {
   return y == 0 ? x : gcd(y, x % y); } int cmp(const void *_p, const void *_q) {
   int *p = (int *)_p, *q = (int *)_q; return a[*p] - a[*q]; } void solve() {
   int i, j, k, t, n, cnt, x, y;     k = (int)sqrt(C + 0.5);     n = 0; for(i = 1; i <= k; i ++)     {
           j = (int)sqrt(C - i * i + 0.5); if(i < j && i * i + j * j == C)         {
               x = j * j - i * i, y = 2 * i * j; if(gcd(x, y) == 1 && gcd(x, C) == 1 && gcd(y, C) == 1)             {
   if(x > y)                     t = x, x = y, y = t;                 a[n] = x, b[n] = y;                     ++ n;             }         }     } for(i = 0; i < n; i ++)         r[i] = i;     qsort(r, n, sizeof(r[0]), cmp); for(cnt = i = 0; i < n; i ++) if(!i || a[r[i]] != a[r[i - 1]])             ++ cnt;     printf("There are %d solution(s).\n", cnt); for(i = 0; i < n; i ++) if(!i || a[r[i]] != a[r[i - 1]])             printf("%d^2 + %d^2 = %d^2\n", a[r[i]], b[r[i]], C); } int main() {
   int t = 0; for(;;)     {
           scanf("%d", &C); if(!C) break;         printf("Case %d:\n", ++ t); if(C % 4 != 1)             printf("There are 0 solution(s).\n"); else             solve();         printf("\n");     } return 0; }