首页 > 搜索 > DFS搜索 > HDU 1111 Secret Code-数论-[解题报告] C++
2013
11-27

HDU 1111 Secret Code-数论-[解题报告] C++

Secret Code

问题描述 :

The Sarcophagus itself is locked by a secret numerical code. When somebody wants to open it, he must know the code and set it exactly on the top of the Sarcophagus. A very intricate mechanism then opens the cover. If an incorrect code is entered, the tickets inside would catch fire immediately and they would have been lost forever. The code (consisting of up to 100 integers) was hidden in the Alexandrian Library but unfortunately, as you probably know, the library burned down completely.But an almost unknown archaeologist has obtained a copy of the code something during the 18th century. He was afraid that the code could get to the “wrong people” so he has encoded the numbers in a very special way. He took a random complex number B that was greater (in absolute value) than any of the encoded numbers. Then he counted the numbers as the digits of the system with basis B. That means the sequence of numbers an, an-1, …, a1, a0 was encoded as the number X = a0 + a1B + a2B2 + …+ anBn.Your goal is to decrypt the secret code, i.e. to express a given number X in the number system to the base B. In other words, given the numbers X and Byou are to determine the “digit” a0 through an.

输入:

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case consists of one single line containing four integer numbers Xr, Xi, Br, Bi (|Xr|,|Xi| <= 1000000, |Br|,|Bi| <= 16). These numbers indicate the real and complex components of numbers X and B, i.e. X = Xr + i.Xi, B = Br + i.Bi. B is the basis of the system (|B| > 1), X is the number you have to express.

输出:

Your program must output a single line for each test case. The line should contain the “digits” an, an-1, …, a1, a0, separated by commas. The following conditions must be satisfied:
for all i in {0, 1, 2, …n}: 0 <= ai < |B|
X = a0 + a1B + a2B2 + …+ anBn
if n > 0 then an <> 0
n <= 100
If there are no numbers meeting these criteria, output the sentence “The code cannot be decrypted.”. If there are more possibilities, print any of them.

样例输入:

4
-935 2475 -11 -15
1 0 -3 -2
93 16 3 2
191 -192 11 -12

样例输出:

8,11,18
1
The code cannot be decrypted.
16,15

题意:给定复数x和复数b,求序列ai使得x=a0+a1*b+a2*b^2+…an*b^n。其中n<=100,|b|>ai>=0,|b|>1.

题解:先吐槽下:有将B^n这么写成Bn的吗,虽然我直接就理解了,可也会害死人的。接着是方法:先要知道复数的运算方法,具体百度,这里只简要说明,复数的模:|Z|=|a+bi|=sqrt(a*a+b*b);复数除法:令t=c*c+d*d,(a+bi)/(c+di)=(ac+bd)/t+(bc-ad)/ti。接着就是化简公式了X=a0+(a1+(a2+…)*b)*b。深搜枚举a0~an,每次减去ai之后除以b后,剩下的就又有一个常数,直到0为止。除法的时候,由于要保证整除(就是上面的ac+bd和bc-ad是t的倍数),可以减少很多时间。数据有点大,用64位__int64。

说句废话:我将if n > 0 then an <> 0 中的an想成了ai,坑了自己半天。。

 

耗时:218MS/1000MS

 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef __int64 LL;
const int maxn=110;
LL xr,xi,br,bi,num;
LL flag,t;
LL ans[maxn];//保存枚举的ai
void dfs(LL rr,LL ii,LL step)
{
    LL x,y,i;
    if (step>100)return;
    if(flag)return;
    if(rr==0&&ii==0)
    {
        flag=1;
        t=step;
        return;
    }
    for(i=0;i*i<num;i++)
    {
	//复数除法运算
        x=(rr-i)*br+ii*bi;
        y=ii*br-(rr-i)*bi;
        ans[step]=i;
        if(x%num==0&&y%num==0)//保证整除
        dfs(x/num,y/num,step+1);
        if(flag)return;
    }
}
int main()
{
    LL T,i;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d%I64d",&xr,&xi,&br,&bi);
        num=br*br+bi*bi;
        flag=0;
        dfs(xr,xi,0);
        if(!flag)printf("The code cannot be decrypted.\n");
        else
        {
            printf("%I64d",ans[t-1]);
            for(i=t-2;i>=0;i--)
            printf(",%I64d",ans[i]);
            printf("\n");
        }
    }
    return 0;
}
/*
1
4 0 2 0
1,0,0
*/

  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。