平方根(sqrt.pas/c/cpp)（数论）

本文主要是介绍平方根(sqrt.pas/c/cpp)（数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平方根(sqrt.pas/c/cpp)

【问题描述】
给出一个正整数 n (1＜n≤2^31-1)，求当 x,y 都为正整数时，方程 的解中， x 最小值为多
少？
√n=√x-√y
【输入文件】
输入文件只有一行，一个正整数 n。
【输出文件】
输出文件只有一行，即满足条件的最小 x 的值。
【文件样例】
sqrt.in sqrt.out
4 9
【数据规模】
30%的数据满足 1＜n≤10000；
100%的数据满足 1＜n≤2^31-1。
【思路】
这个题刚开始是暴力算法。
X=Y+N+2√(YN)
也就是求使得NY为完全平方数的最小的Y，于是我就用了一个O(N)的算法，最后超时过3个点。
接下来的方法首先是一个推导过程：
X=N+Y+2√(YN)
=(√N+√Y)^2
=(P√Y+√Y)^2
=P^2*Y+Y+2*P*Y
=(P+1)^2*Y
这里的Y就是最小的那个Y，而要求这个Y就是求N%(Y*Y)=0的Y。
最后输出(P+1)^2*Y即可。
【代码】

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
long long i,j,m;
long long n;int r()
{int ans=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
//      if(ch=='-')
//      f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){ans*=10;ans+=ch-'0';ch=getchar();}return ans*f;
}int main()
{freopen("sqrt.in","r",stdin);freopen("sqrt.out","w",stdout);scanf("%lld",&n);long long now,lsq,y,x;for(i=(int)sqrt(n);i>=1;i--)if (n%(i*i)==0){y=n/(i*i);break;}x=(i+1)*(i+1)*y;cout<<x<<endl;}
/*
1000000000
*/

这篇关于平方根(sqrt.pas/c/cpp)（数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---