7-21 求特殊方程的正整数解

本题要求对任意给定的正整数$N$，求方程$X^2+Y^2=N$的全部正整数解。

输入格式

输入在一行中给出正整数$N$（≤10000）。

输出格式

输出方程$X^2+Y^2=N$的全部正整数解，其中$X\le Y$。每组解占1行，两数字间以1空格分隔，按$X$的递增顺序输出。如果没有解，则输出No Solution。

输入样例1

884

输出样例1

10 28
20 22

输入样例2

11

输出样例2

No Solution

分析与答案

$N\le 10000$，所以$X\le Y\le 100$，题目要求按$X$的递增顺序输出，所以程序中$Y$从100开始往下循环，每次循环，$X$都在第二层从1开始往上循环到$Y$，每次满足题目条件就为计数变量加一并输出。输出换行符与否也以计数变量判断。如果循环结束了计数变量还是0，说明无解，输出No Solution。

#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    int x = 0, y = 0, sol = 0;
    for (y = 100;y >= 1;y--){
        for(x = 1;x <= y;x++){
            if(x*x+y*y == n){
                sol++;
                if(sol!=1) 
                    printf("\n");
                printf("%d %d",x,y);
            }
        }
    }
    if(sol == 0)
        printf("No Solution");
    return 0;
}