【Comet OJ - Contest #0 A】解方程（数学水题）

点此看题面

大致题意： 给定自然数\(n\)，让你求出方程\(\sqrt{x-\sqrt n}+\sqrt y-\sqrt z=0\)的自然数解\(x,y,z\)的数量以及所有解\(xyz\)之和。

推式子

这道题应该不是很难。

移项可以得到：

\[\sqrt{x-\sqrt n}=\sqrt z-\sqrt y
\]

两边同时平方：

\[x-\sqrt n=y+z-2\sqrt {yz}
\]

则我们可以得出第一个结论：

当\(n\)为完全平方数，即\(\sqrt n\)为整数时，有无数组解，直接输出\(infty\)。

否则，我们可知：

\[\begin{cases}x=y+z,&①\\\sqrt n=2\sqrt{yz}&②\end{cases}
\]

其中，对于\(②\)式，我们再同时平方得到：

\[n=4yz
\]

有了这个式子，加上前面\(①\)式中得出的\(x=y+z\)，我们就可以轻松得出结论：

若\(n\)不为\(4\)的倍数，则无解，直接输出"0 0"。

否则的话，我们就\(O(\frac{\sqrt n}2)\)枚举\(y\)（由原式易知\(y<z\)），然后就可以求出答案了。

具体实现详见代码。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define X 1000000007

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

using namespace std;

int n;

int main()

{

	RI Ttot,i,ans1,ans2;scanf("%d",&Ttot);W(Ttot--)

	{

		if(scanf("%d",&n),(int)sqrt(n)*(int)sqrt(n)==n) {puts("infty");continue;}//若n为完全平方数，有无数组解

		if(n%4) {puts("0 0");continue;}//若n不为4的倍数，无解

		for(n/=4,ans1=ans2=0,i=1;1LL*i*i<=n;++i) !(n%i)&&(++ans1,Inc(ans2,1LL*n*(i+n/i)%X));//枚举y，统计答案

		printf("%d %d\n",ans1,ans2);//输出

	}return 0;

}

巴特西

【Comet OJ - Contest #0 A】解方程（数学水题）

推式子

代码

最新文章

热门文章