方程式

题目描述

“告诉你们一件事吧。当地面充满 100 万只猴子的时候, 月球将化作地狱的使者, 毁灭螺旋之星。”留下了最后一句话的罗杰诺姆, 于特佩林跌向天空。西蒙与妮亚都不明白罗杰诺姆留下的话的含义。不过后来, 他们唯一明白的是, 战斗结束了。并且, 崭新的日子正在等待着他们。
这是一个, 即使遭到了命运背叛, 仍然继续寻找自己前进道路的男人的故事——王都特佩林功防战 7 年后, 特佩林更名为神名市, 人类以此作为复兴的象征, 并且得到了繁荣。罗杰
诺姆积蓄下来的技术也支撑着人们的繁荣。
和平与繁荣之名下的懈怠与弛缓。人们忘记了当年的穴居生活, 如今只是一味地享受幸福。独自支撑
着新政府的罗修, 对人们的愚蠢感到无尽的焦虑。
于是, 在西蒙向妮亚求婚的这一天, 人类的第 100 万名终于降生于世。
天空中回响着冰冷彻骨的声音。“告地球人类。我等反螺旋族 Anti-Spiral 断定, 地球人类的螺旋力危险水平已经进入第二阶段。人类歼灭系统就此启动。”
为了拯救人类, 西蒙决定用手中的钻头开启螺旋族曾经的战舰月球而开启战舰的密码正是镌刻在月球上的方程式的所有的解，只需要将这个方程的所有的解按从小到大的顺序依次输出，便可以开启月球西蒙已经没有多少时间了, 他只能求助你
Input
第一行一个数表示这是一个 n 次方程
第二行共 n + 1 个数，第 i 个数 ai 表示 x
i?1 前的系数，最高次项前系数一定为 1
Output
一行 n 个数，从小到大依次输出方程的 n 个解
如果是重根也要输出，数据保证方程的所有解都是小于等于 20 的正整数
Example

-2 5 -4 1

1 1 2

8 -20 18 -7 1

1 2 2 2

2 -3 1 
1 2

分析：

思路一：

　　一开始的思路：刚开始画了一个函数曲线图像...像这样：

　　然后感觉如果一个x值对应的y值一边小于0，一边大于0（蓝色）就没有重根，如果两边都大于0或两边都小于0就有重根

　　打完了之后发现不对...因为像${(x-2)}^2=0$这样的方程有三个重根...显然这样的方法是有缺陷的...

思路二：

　　最高次项的系数为1且所有解都是正整数，不难联想到这样的形式（以三次为例）：

$(x-a)*(x-b)*(x-c)$

暴力拆它：

${x}^3-(a+b+c)x^2+(ab+ac+bc)x-abc$

再看一下四次的

$(x-a)(x-b)(x-c)(x-d)=$

$x^4-(a+b+c+d)x^3+(ab+ac+ad+bc+bd+cd)x^2-(abc+abd+bcd)x+abcd$

我们发现根和系数是有关系的...假设a[i]存的是i次项系数则

(奇偶判断)${x}_1*{x}_2*{x}_3*{x}_4...*{x}_n=a[0]$

$-({x}_1+{x}_2+{x}_3+{x}_4...+{x}_n)=a[n-1]$

令$s={x}_1*{x}_2*{x}_3*{x}_4...*{x}_n$

则$s/{x}_1+s/{x}_2+s/{x}_3+...+s/{x}_n=a[1]$

复杂度分析：我们可以用搜索确定每一个${x}_1,{x}_2$……,每个根在1~20内，则复杂度$O(20^7)$

显然不可行...然后我们根据第一个等式关系可以发现我们只要求${x}_1,{x}_2...{x}_{n-1}$即可，${x}_n$减一下就出来了

然后再判断这些解是否满足另外两个等式关系...满足就可以退出了

复杂度$O(n*20^6)$,显然是跑不满的...跑起来大概只有一半

 1 #include<cstdio>
 2 #include<queue>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cmath>
 7 using namespace std;
 8 inline int read(){
 9     int ans=0,f=1;char chr=getchar();
10     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
11     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
12     return ans*f;
13 }int n,a[10],ANS[10],tot;int ff=0;
14 inline bool check(){
15     int s=0,p=1;
16     for(int i=1;i<=n-1;++i) s+=ANS[i],p*=ANS[i];
17     ANS[n]=-a[n-1]-s;//得到${x}_n$
18     p*=ANS[n];
19     if(ANS[n]==0) return 0;
20     if(ANS[n]>20||ANS[n]<0) return 0;//显然不可行
21     if(n&1) p=-p;//奇偶性判断
22     if(p!=a[0]) return 0;//第二个等式
23     if(n&1) p=-p;
24     s=0;
25     for(int i=1;i<=n;i++){
26         int t=p/ANS[i];
27         s+=t; 
28     }
29     if(n&1^1) s=-s;
30     if(s==a[1]) ff=1;//第三个等式
31 }
32 void dfs(int x){
33     if(ff) return;
34     if(x==n){
35         check();
36         if(ff){
37             sort(ANS+1,ANS+n+1);//排序
38             for(int i=1;i<=n;i++)
39                 cout<<ANS[i]<<" ";
40             return;
41         }return;
42     }
43     if(x&1)//担心会被卡...搜索顺序乱搞一下,不这样也可以
44         for(int i=1;i<=20;i++)
45             ANS[x]=i,dfs(x+1);
46     else for(int i=20;i>=1;i--) ANS[x]=i,dfs(x+1);
47 }
48 int main(){
49     n=read();
50     for(int i=0;i<=n;i++) a[i]=read();
51     dfs(1);
52     return 0;
53 }
54 /*
55 3
56 -2 5 -4 1 
57 
58 4
59 8 -20 18 -7 1 
60 */