1 条题解
-
0
思路 参考了一下别人的思路: 暴力搜索,把要搜索的序列{an}想成一个森林,a0在第一层,a1在下一层,以此类推.
秦九韶算法:x=a0+(a1+(a2+(a3+…)*b)*b)*b,容易想到递归实现.
为了方便运算,把实部、虚部拆开一起递归,每次递归枚举下一层a(i+1)的所有可能结果,很容易想到{an}必定都为整数序列,每枚举一个a(i+1),判断[X-a(i)]%b能否整除(实部与实部、虚部与虚部),满足继续dfs,不满足继续枚举,直到Xr0,Xi0递归结束,当然不能超过100层。最后得到的序列逆序输出即可
#include<iostream> #include<algorithm> #include<stdio.h> #include<queue> #include<set> #include<map> #include<string> #include<memory.h> using namespace std; int xr,xi,br,bi,con; int flag,t; int a[105]; void dfs(int n) { int x,y,i; if(n>100)//多项式最多00项 return ; if(xr==0&&xi==0) { flag=1; t=n; return ; } for(i=0;i*i<con;i++) { //xi减去a[i]后剩下的部分,根据复数的除法运算可以得到如下表达式 x=x+yi; x=(xr-i)*br+xi*bi; y=xi*br-(xr-i)*bi; a[n]=i; if(x%con==0&&y%con==0)//保证整除 { xr=x/con; xi=y/con; dfs(n+1); } if(flag) return ; } } int main() { int T; cin>>T; while(T--) { cin>>xr>>xi>>br>>bi; con=br*br+bi*bi; flag=0; dfs(0); if(!flag) { cout<<"The code cannot be decrypted."<<endl; }else { cout<<a[t-1]; for(int i=t-2;i>=0;i--) { cout<<','<<a[i]; } cout<<endl; } } return 0; }
- 1
信息
- ID
- 382
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者