51Nod 1080 两个数的平方和(数论,经典题)

简介: 1080 两个数的平方和                 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题                 给出一个整数N,将N表示为2个整数i j的平方和(i
               
基准时间限制:1 秒 空间限制:131072 KB 分值: 5        
   
            

给出一个整数N,将N表示为2个整数i j的平方和(i <= j),如果有多种表示,按照i的递增序输出。

 
例如:N = 130,130 = 3^2 + 11^2 = 7^2 + 9^2 (注:3 11同11 3算1种)
   
       
Input
       
一个数N(1 <= N <= 10^9)
       
Output
       
共K行:每行2个数,i j,表示N = i^2 + j^2(0 <= i <= j)。
如果无法分解为2个数的平方和,则输出No Solution
       
Input示例
       
130
       
Output示例
       
3 11
7 9
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1080
分析:又是一道大数据易超时的题,怎么做呢,降低复杂度,我的办法是让复杂度为O(n^1/2)处理,刚开始觉得不会超,复杂度为O(n),结果超时了几组数据,诶,还是很菜啊,得加油!
下面给出AC代码:
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5    int T;
 6    while(scanf("%d",&T)!=EOF)
 7    {
 8        int flag=0;
 9        for(int i=0;i<=sqrt(T+0.5);i++)
10        {
11            int j=sqrt(T-i*i);
12            if(pow(i,2)+pow(j,2)==T&&i<=j)
13            {
14                    flag=1;
15                    printf("%d %d\n",i,j);
16            }
17        }
18        if(!flag)
19         printf("No Solution\n");
20    }
21    return 0;
22 }

 

目录
相关文章
|
2天前
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
【每日一题Day358】LC2698求一个整数的惩罚数 | 递归
20 0
|
2天前
考研高数之无穷级数题型一:判断收敛性、求收敛半径以及收敛域和收敛区间(题目讲解)
考研高数之无穷级数题型一:判断收敛性、求收敛半径以及收敛域和收敛区间(题目讲解)
97 0
|
12月前
51nod 1189 阶乘分数(数论)
51nod 1189 阶乘分数(数论)
36 0
【每日一题Day63】LC1753移除石子的最大得分 | 贪心 + 数学
当对a,b,c进行升序排序后,如果a+b≥c,应先优先让a 和b去匹配,匹配的次数为a+b−c,得分为count=⌈(a+b−c)/2⌉
79 0
|
存储 机器学习/深度学习 人工智能
【Python 百练成钢】DNA、蛇形矩阵、Huffuman树、K-进制数、K倍区间、交换瓶子、第几个幸运数、四平方和、The 3n + 1 problem、大数乘法
【Python 百练成钢】DNA、蛇形矩阵、Huffuman树、K-进制数、K倍区间、交换瓶子、第几个幸运数、四平方和、The 3n + 1 problem、大数乘法
245 0
【Python 百练成钢】DNA、蛇形矩阵、Huffuman树、K-进制数、K倍区间、交换瓶子、第几个幸运数、四平方和、The 3n + 1 problem、大数乘法
|
机器学习/深度学习 算法
卡特兰数(Catalan Number) 算法、数论 组合~
卡特兰数(Catalan Number) 算法、数论 组合~
203 0
卡特兰数(Catalan Number) 算法、数论 组合~
[解题报告]《算法零基础100讲》(第11讲) 因子数
[解题报告]《算法零基础100讲》(第11讲) 因子数
[解题报告]《算法零基础100讲》(第11讲) 因子数
|
算法 C语言 UED
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
[解题报告]《算法零基础100讲》(第1讲) 幂和对数
数论--错排
先上唯一看得懂的错排概念,大概像递推dp一样?分情况分步骤往上级递推出的公式
89 0
数论--错排