一种求一定有正整数解的高次方程的方法

· · 算法·理论

起源

关于为什么要写这篇文章,是因为牛顿迭代法建立在导数的基础上,因而不好理解,需要用到微积分。

所以结合一些定理和本人平时解方程的经验有了这种方法。

限制

仅限一个高次方程有正整数解时使用,但效率较高。

前置数学知识

余式定理:一多项式 f(x) 除以一线性多项式 (x-a) 的余式为 f(a)

证明:我们设 f(x)=g(x)(x-a)+r(x)

由于 r(x) 的次数必然低于除式 (x-a),故 r(x)x0 次,即 r(x) 为一常数 r

我们将 x=a 代入上式,则有 f(a)=g(a)(a-a)+r(a)=r(a)=r,证毕。

拓展定理:因式定理:若一实数 \alpha 为多项式 f(x) 的根,则以 (x-\alpha)f(x) 无余数,即存在 g(x) 使得 f(x)=g(x)(x-\alpha)

证明:由余式定理,得 f(x)=g(x)(x-\alpha)+f(\alpha)=g(x)(x-\alpha),证毕。

再拓展定理:一多项式函数 f(x) 若全为整数根,则其整数根必为其常数项的因数或其相反数。

证明:由因式定理,我们设 x_1,x_2,\dots,x_nn 次多项式 f(x) 的根,则有 \prod\limits_{i=1}^n(x-x_i)=f(x),展开即有 \prod\limits_{i=1}^nx_if(x) 的常数项。

又由 x_i 为整数,故 x_if(x) 的常数项的因数或其相反数。

算法实现

对于函数 f(x),我们枚举其常数项的因数,并依次尝试 f(a) 是否等于 0,复杂度 O(n\log n\sqrt{n})

代码

#include<bits/stdc++.h>
using namespace std;
int n,a[10010];
int qpow(int base,int up){
    int ans=1;
    while(up){
        if(up&1){
            ans*=base;
        }
        base*=base;
        up>>=1;
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n+1;i++){
        cin>>a[i];
    }
    for(int i=1;i<=sqrt(a[n+1]);i++){
        if(a[n+1]%i==0){
            int sum=0;
            for(int j=1;j<=n+1;j++){
                sum+=a[j]*qpow(i,n-j+1);
            }
            if(sum==0){
                cout<<i<<" ";
            }
        }
    }
    return 0;
}