PTA基础编程题目集 7-21求特殊方程的正整数解（C++语言实现）

摘要本文是PTA编程题求特殊方程的正整数解的题解涵盖题目描述、输入输出格式及C语言实现展示双重枚举暴力搜索算法。题目描述本题要求对任意给定的正整数N求方程X² Y² N的全部正整数解。输入格式输入在一行中给出正整数N≤10000。输出格式输出方程X² Y² N的全部正整数解其中X≤Y。每组解占1行两数字间以1空格分隔按X的递增顺序输出。如果没有解则输出No Solution。输入样例88411输出样例10 28 20 22No Solution解题思路核心问题分析给定正整数N找出所有满足X² Y² N且X≤Y的正整数对(X, Y)。由于N最大为10000X和Y的最大值都不超过100暴力枚举完全可行。算法原理采用双重循环枚举法。外层循环枚举X从1到√N内层循环枚举Y从X到√N对每对(X, Y)判断是否满足方程X² Y² N。Y从X开始枚举保证了X≤Y的约束条件。具体计算步骤读取正整数N初始化标记found0表示未找到解X从1开始递增直到X² N为止对每个XY从X开始递增直到Y² N为止若X² Y² N输出该组解并标记found1遍历结束后若found仍为0输出No Solution代码流程说明变量声明定义N存储输入值X、Y为循环变量found标记是否找到解输入读取使用cin读取正整数N外层循环X枚举X从1开始循环条件X*X ≤ N每次X自增1内层循环Y枚举Y从X开始循环条件Y*Y ≤ N每次Y自增1方程判断若XX YY N则输出X和Y设置found1无解判断双重循环结束后若found为假输出No Solution程序结束返回0代码流程图否是否是是否是否开始声明变量N,X,Y,found0输入NX1X*X N?found0?YXY*Y N?XX*XY*Y N?输出X Y, found1Y输出No Solution结束解题流程图否是否是是否是否输入正整数NX1X² N?是否找到解?YXY² N?XX²Y² N?输出X Y标记找到解Y正常结束输出No Solution代码部分实现#includeiostreamusingnamespacestd;intmain(void){intN,X,Y,found0;// N为给定的正整数X和Y为方程的解found标记是否找到解cinN;// 读取正整数N// 枚举X和Y的值寻找满足X²Y²N的正整数解for(X1;X*XN;X){// X从1遍历到sqrt(N)for(YX;Y*YN;Y){// Y从X遍历到sqrt(N)保证X≤Yif(X*XY*YN){// 检查是否满足方程coutX Yendl;// 输出一组解found1;// 标记已找到解}}}if(!found){// 未找到任何解coutNo Solutionendl;// 输出无解提示}return0;}