综合分析法:
要想 是正整数,那么只能 与 同时为完全平方数, 选取的种类完全决定了正整数对 的数量,反过来也是如此。
设 , ,
也就是说, 的种类数目等于 拆为两约数之积的分解数目。记为
我们规定 ,也就是说出现交换的情况只算一次。
而一个正整数的分解是有限的,于是通过列出不同的约数组合,得到线性方程组:
解得
这就需要 与 奇偶性相同,于是对于 一奇一偶的因数拆分,我们可以直接排除这种情况。
而对于一般情况,设 的质因数分解式为
,
综上,
其中,
解:由上面的定义 , ,其中 ,算得共有整数解:
事实上,当
也即是当
解: , ,其中 ,算得共有整数解:
之所以举这个例子,是想体现 为 (偶数情况)时,上面公式的前一项为
事实上 可取值
对于 的取值范围,我给出一个很粗略的界,方便程序跑循环
我将 和 全都放大为 ;至于下界,
综上,
#约数列表 dlist<-function(n) { ans=c() for(j in 1:n) { if((n%%j)==0){ans=c(ans,j)} } ans } #求因子p的指数 index<-function(n,p) { r=n;m=log(n,p) if(m%%1==0)return(m) for(j in 0:m) { if(r%%p!=0)return(j) r=r/p } return(j) } #非负取整函数 pf<-function(x) { if(x>0){y=floor(x)}else{y=0} y } #方程y=sqrt(x+a)+sqrt(x+b)整数解个数(理论计算) Key<-function(a,b) { K=abs(a-b) alpha=index(K,2) L=K/2^alpha dL=length(dlist(L)) if(alpha%%2==0) { ans=pf(alpha/2-1)*dL+floor(dL/2) }else{ ans=floor(alpha/2)*floor(dL) } ans } fx<-function(a,b,x) { y=sqrt(x+a)+sqrt(x+b) y } #方程y=sqrt(x+a)+sqrt(x+b)整数解个数(数值验证) key<-function(a,b) { K=abs(a-b);m=min(a,b) for(j in -m:(K^2-m)) { if(fx(a,b,j)%%1==0)print(j) } }
利用程序可以进行数值验证。
如何快速求一个正整数 的约数(已知质因数分解):
这是初等数论里的一个结论,证明利用的是计数原理中的乘法分步原理。