首页 > ACM题库 > HDU-杭电 > HDU 4143-A Simple Problem-数学相关-[解题报告]HOJ
2015
04-16

HDU 4143-A Simple Problem-数学相关-[解题报告]HOJ

A Simple Problem

问题描述 :

For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2.

输入:

The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).

输出:

The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).

样例输入:

2
2
3

样例输出:

-1
1

/*
摘:
    解题思路:如果要按正常方法从小到大遍历,由于数据量大一定会超时。
其实上述式子转化后可以分解因子:n = ( y – x )*( y + x ) ;
令 y – x = i,所以有 x + y = n / i ,即 ( n / i – i ) / 2 = x.
    注意:x 要大于 0 ,当 n 是完全平方数时要注意。

                                                   2012-04-21
*/

#include"stdio.h"
#include"math.h"
int main()
{
	int i;
	int t;
	int n;
	int x;
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		x=-1;
		t=(int)sqrt(n);
		for(i=t;i>0;i--)
		{
			if(n%i==0&&(n/i-i)%2==0&&(n/i-i)/2>0)
			{
				x=(n/i-i)/2;
				break;
			}
		}


		printf("%d\n",x);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7484167


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?