「题解」解方程

求高次方程$a_0+a_1x+a_2x^2+a_3x^3+…+a_nx^n=0$在区间$[1,m]$内的所有整数解……

一 题目

原题链接

描述

如题，求高次方程$a_0+a_1x+a_2x^2+a_3x^3+…+a_nx^n=0$在区间$[1,m]$内的所有整数解。

数据范围：$n\leqslant 100,|a_i|\leqslant 10^{10000},a_n\ne 0,m< 10^6$

---

二 题解

数据范围一看就是坑。首先$n\leqslant 100,m< 10^6$，那么就可以枚举答案，每次花$O(n)$的时间去验证答案的正误。但是系数太大了！高次方程又不存在通解公式，那我们只能把系数模大质数以储存下来。

分析

不妨将方程看作函数。
设高次函数$f(x) = a_0+a_1x+a_2x^2+a_3x^3+…+a_nx^n$，然后我们要把$a_0\text{~}a_1$都模$R$，也就是把原函数变成$f’(x) = a_0\text{ mod } R+(a_1\text{ mod } R)x+(a_2\text{ mod } R)x^2+(a_3\text{ mod } R)x^3+…+(a_n\text{ mod } R)x^n$。实际上这个函数应该在对$R$取模的情况下才有意义（即在取模意义下与$f(x)$大致重合）。

验证
画出了$f(x) = 879+653x+597x^2+497x^3+432x^4+421x^5$的图像，$r(x)=f(x)\text{ mod }397$的图像和$f’(x) = (85+256x+200x^2+100x^3+35x^4+24x^5)\text{ mod }397$的图像。
其中，对于相同的$x$，总存在$f(x) \equiv r(x)(\text{mod }397)$。而$r$与$f’$基本重合，故推出：若有$x$使得$f’(x)=k$，那么$f(x)\equiv k(\text{mod }397)$有几率成立。

但是别忘了：我们推出来的只是同余。也就是说，只是有几率会有$f’(x)=k \Rightarrow f(x)\equiv k (\text{mod }R)$，实际上$f(x)$不一定恰好等于$k$。所以为了避免这个问题，$R$不妨选的大一点，然后最好是质数。当然，为了保证准确，也可以多选择几个$R$值，不过这会拖慢程序运行效率。

回到题目

那么不妨选取两个大质数$R_1,R_2$，然后得到两个系数分别模$R_1,R_2$的函数$f’_1,f’_2$。枚举$x\in [1,m]$，若对于同一个$x$，有$f’_1(x)=f’_2(x)=0$，则基本可以断定$x$是我们想要的解。

但是还要考虑运行效率。取余运算是很慢的，而算法复杂度为$O(nm)$，最高$O(10^8)$，再乘上一个大常数，无疑会TLE。但是可以发现，若$f’(x)\text{ mod } R=0$，则一定有$f’(x+kR)\text{ mod } R=0$。

证明
把$a_n(x+kR)^n$展开，得：
$$ \begin{aligned} a_n(x+kR)^n &= a_n[x^n+ b_1x^{n-1}kR + …+b_{n-1}x(kR)^{n-1}+(kR)^n] \newline & = a_nx^n + a_nb_1x^{n-1}kR+ … + a_nb_{n-1}x(kR)^{n-1}+a_n(kR)^n\end{aligned}$$
其中$(a_nb_1x^{n-1}kR+ … + a_nb_{n-1}x(kR)^{n-1}+a_n(kR)^n )\text{ mod } R = 0$，因为都可以提出因式$kR$。
所以得：
$$ a_n(x+kR)^n \equiv a_nx^n (\text{mod }R) $$
一般情况证明完成，也就是说对于任意正整数$n$都满足上面的式子。
故$a_1\text{}a_n$都分别同余于$a_1(x+kR)\text{}a_n(x+kR)^n$。那么一定有$f’(x) \equiv f’(x+kR) (\text{mod }R)$。

所以我们只需要枚举$k\in [1,R_1)$，处理出有哪些$k$，使$f’_1(k)=0$。然后再枚举$i\in [1,m]$，若$i\text{ mod }k=0$且$f’_2(i)=0$，则断定$i$是解。

附：常用大质数
1e5+7,99991,1e8+7,1e9+7,998244353。

代码，其实long long可以不开。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;

#define LL long long

const int CN = 110;

const int R1 = 99991; //R1小一点，提高运行效率
const int R2 = 1e8+7; //R2大一点，提高精度

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

int n,m;
LL a1[CN],a2[CN]; //f1,f2的系数
bool is[CN*CN*CN]; //is[x] : 判断f1(x)是否为0
int ans[CN*CN*CN];

void aread(int i){
    LL ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()){
        a1[i]=((a1[i]<<1)+(a1[i]<<3)+c-'0')%R1; //记录系数
        a2[i]=((a2[i]<<1)+(a2[i]<<3)+c-'0')%R2;
    }
    a1[i] *= ne;
    a2[i] *= ne;
}

bool calc(LL x,int R,LL* a){
    LL f = 0; //f(x)
    for(int i=n;i;i--)
        ((f += a[i]) *= x) %= R; //秦九韶公式
    (f += a[0]) %= R; //只有在取模意义下上面的推导才会成立
    return !f;
}

int main()
{
    n = read(); m = read();
    for(int i=0;i<=n;i++) aread(i);
    
    for(LL i=1;i<R1;i++)
        if(calc(i,R1,a1)) is[(int)i] = true;
    for(LL i=1;i<=m;i++)
        if(is[(int)i%R1] && calc(i,R2,a2)) ans[++ans[0]] = i; //记录答案
    
    printf("%d\n",ans[0]);
    for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]);
    
    return 0;
}