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

1080 两个数的平方和

基准时间限制:1 秒 空间限制:131072 KB 分值: 5        

难度:1级算法题

给出一个整数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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与计算机视觉

TensorFlow 网络优化步骤与一般方法

深度学习中,网络的优化是训练过程中很重要的一部分,现在有很多的优化策略,而他们的核心的内容都是梯度下降。 理论的部分大家可以参考: 理解梯度下降在机器学...

57610
来自专栏求索之路

cs231n之KNN算法

1.环境搭建以及前置条件 1.前置环境: 1.mac 2.pycharm 3.python3 4.Anaconda 2.环境搭建: 1.官网下载并安装Ana...

3339
来自专栏数据小魔方

撬动地球需要一个杠杆,看懂图表需要一条参考线

今天要跟大家介绍一下图表中用作对比的参考线制作技巧 ▽ 参考线能够更明显的 突出真实值与目标值之间的差距 ? ? 今天要介绍两种参考线的制作思路 散点图法——...

2886
来自专栏fangyangcoder

tensorflow笔记(四)之MNIST手写识别系列一

http://www.cnblogs.com/fydeblog/p/7436310.html

1281
来自专栏Petrichor的专栏

matplotlib: 绘制平面图/表格

2384
来自专栏菩提树下的杨过

WPF中的MatrixTransform

WPF中的MatrixTransform            周银辉 虽然在WPF中可以使用TranslateTransform、RotateTrans...

20410
来自专栏Jack-Cui

Caffe学习笔记(三):cifar10_quick_train_test.prototxt配置文件分析

运行平台: Ubuntu14.04     在上篇笔记中,已经记录了如何进行图片数据格式的转换和生成txt列表清单文件。本篇笔记主要记录如何计算图片数据的均值和...

3018
来自专栏Spark学习技巧

译:Tensorflow实现的CNN文本分类

1655
来自专栏Small Code

【TensorFlow】TensorFlow 的卷积神经网络 CNN - 无TensorBoard版

前面 有篇博文讲了多层感知器,也就是一般的前馈神经网络,文章里使用 CIFAR10 数据集得到的测试准确率是 46.98%。今天我们使用更适合处理图像的卷积神经...

2717
来自专栏用户2442861的专栏

tensorflow CNN mnist 示例

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/d...

2442

扫码关注云+社区