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

RAY091016 · 2025-01-23 08:07:44 · 算法·理论

起源

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

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

限制

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

前置数学知识

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

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

由于 r(x) 的次数必然低于除式 (x-a)，故 r(x) 中 x 为 0 次，即 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_n 为 n 次多项式 f(x) 的根，则有 \prod\limits_{i=1}^n(x-x_i)=f(x)，展开即有 \prod\limits_{i=1}^nx_i 为 f(x) 的常数项。

又由 x_i 为整数，故 x_i 为 f(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;
}