【HDU】 1111 Secret Code

2024-03-09 06:48

文章标签 code hdu secret 1111

本文主要是介绍【HDU】 1111 Secret Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Secret Code

题目链接

Secret Code

题目大意

不得不说题意挺难懂的…
首先题目有一个式子：

X = a 0 + a 1 * B + a 2 * B 2 + . . . + a n * B n

$X=a_0+a_1*B+a_2*B^2+...+a_n*B^n$
在这里X和B都是一个复数，现在告诉你X和B，让你求出是否有一组整数

a0 $a_0$ ~

an $a_n$ 满足这个等式，如果有，请输出

an $a_n$ ~

a0 $a_0$ （真是烦还要倒着输出 : ( ）

题解

一道看上去很繁琐的题目，第一眼看上去好像无从下手，但是我们分析这个公式，我们把公式中的B逐次提出，现在公式就变成了这个样子

X = a 0 + (a 1 + (a 2 + (. . .) * B) * B) * B

$X=a_0+(a_1+(a_2+(...)*B)*B)*B$
我们发现：只要我们把

a0 $a_0$ 移到左边，在除B，这个式子右边的结构竟然没有发生变化！这就为我们提供了搜索的可能，我们看到B的模大概是22左右，100*22=2200，这个规模是可搜的，于是我们这里采用了DFS来搜每一位的值，直到X等于零为止。
最后才发现这是秦九韶…

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long longusing namespace std;LL xr,xi,br,bi,mod,n,T,path[105];
bool flag;void dfs(LL xr,LL xi,LL d)
{LL a,b;if (d>101) return ;if (xr==0 && xi==0){flag=1; n=d-1;return ;}for (LL i=0;i*i<=mod;i++){a=(xr-i)*br+bi*xi;b=xi*br-(xr-i)*bi;if (a%mod==0 && b%mod==0){path[d]=i;dfs(a/mod,b/mod,d+1);if (flag) return;}}
}int main()
{scanf("%I64d",&T);while(T--){memset(path,0,sizeof(path));scanf("%I64d%I64d%I64d%I64d",&xr,&xi,&br,&bi);mod=br*br+bi*bi;flag=0;dfs(xr,xi,0);if (flag){for (int i=n;i>0;i--) printf("%I64d,",path[i]);printf("%I64d",path[0]);printf("\n");}else printf("The code cannot be decrypted.\n");}return 0;
}