「题解」解方程

「题解」解方程

求高次方程$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)$有几率成立。

二.1(1) 函数图像

但是别忘了:我们推出来的只是同余。也就是说,只是有几率会有$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可以不开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#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;
}
作者

ce-amtic

发布于

2019-07-12

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×