首页 > 代码库 > HDU 1111 Secret Code (DFS)

HDU 1111 Secret Code (DFS)

2024-08-04 14:58:08   218人阅读

题目链接

题意 ： 给你复数X的Xr和Xi，B的Br和Bi，让你求一个数列，使得X = a0 + a1B + a2B2 + ...+ anBn，X=Xr+i*Xi，B=Br+Bi*i ；

思路 ： 首先要知道复数的基本运算，题目中说0 <= ai < |B| ，|B|代表的是复数的模，|B|=√（Br*Br+Bi*Bi）。将题目中给定的式子X = a0 + a1B + a2B2 + ...+ anBn，进行变型得：X=a0 + （a1 + （a2 + ...（an-1+ an*B））） 。所以这里深搜枚举a的值，从X开始减掉a再除以B，然后看是否成立，是否都为整数，因此要用到复数的除法：(a+bi)/(c+di)=(ac+bd)/(c^2+d^2)+(bc-ad)/(c^2+d^2) ;

 1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #define   LL __int64 5 using namespace std ; 6  7 LL xr,xi; 8 int br,bi ; 9 LL a[110] ,st;10 bool flag ;11 void dfs(LL r,LL i,int step)12 {13     if(step > 100) return ;14     if(flag) return ;15     if(r == 0 && i == 0)16     {17         flag = true ;18         st = step ;19         return ;20     }21     for(int j = 0 ; j * j < br*br+bi*bi ; j++)22     {23         LL xx = (r-j)*br+i*bi;24         LL yy = (i*br)-(r-j)*bi;25         a[step] = j ;26         if(xx % (br*br+bi*bi) == 0  && yy % (br*br+bi*bi) == 0)27             dfs(xx / (br*br+bi*bi) , yy / (br*br+bi*bi),step+1) ;28         if(flag) return ;29     }30 }31 int main()32 {33     int T;34     scanf("%d",&T) ;35     while(T--)36     {37         memset(a,0,sizeof(a)) ;38         st = 0 ;39         flag = false ;40         scanf("%I64d %I64d %d %d",&xr,&xi,&br,&bi) ;41         dfs(xr,xi,0) ;42         if(!flag) puts("The code cannot be decrypted.");43         else {44             printf("%I64d",a[st-1]) ;45             for(int i = st-2 ; i >= 0 ; i -- )46             {47                 printf(",%I64d",a[i]) ;48             }49             puts("") ;50         }51     }52     return 0 ;53 }
View Code

 

HDU 1111 Secret Code (DFS)


联系
我们