1 条题解

  • 0
    @ 2025-4-17 15:47:06

    思路 参考了一下别人的思路: 暴力搜索,把要搜索的序列{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
    上传者