[HDU 1111]--Secret Code
10585 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1111
Problem Description
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.
Input
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.
Output
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.
Sample Input
4
-935 2475 -11 -15
1 0 -3 -2
93 16 3 2
191 -192 11 -12
Sample Output
8,11,18
1
The code cannot be decrypted.
16,15
Source
Central Europe 1999
あなたに2つの複素xをあげて、b(xr、xi、br、biは実数に対応して、虚数の部分)は1つのシーケンスaが満たすことを求めます X = a0 + a1B + a2B^2 + ...+ anB^n
考え方:この問題はずっと穴に落ちていますね.私たちの学校ではずっとwaをしています. データの問題を疑って杭電に行ってブラシをかけた(事実は私が考えすぎたことを証明した(.・＿・.)ﾉ)
まずはコープに来て
秦九韶アルゴリズム:
n次多項式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]
次のように書き換えます.
f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]
=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]
=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]
=...... =(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].
多項式の値を求める場合、まず最内層括弧内の一次多項式の値、すなわちv[1]=a[n]x+a[n-1]を計算し、次に内向外から層毎に一次多項式の値、すなわち v[2]=v[1]x+a[n-2] v[3]=v[2]x+a[n-3] ...... v[n]=v[n−1]x+a[0]のように、n次多項式f(x)を求める値は、n個の一次多項式を求める値に変換される.(注:中括弧の数は下付きを表す)上記の方法を秦九韶アルゴリズムと呼ぶ.今日に至るまで、このアルゴリズムは多項式の評価が比較的先進的なアルゴリズムである.
複素数の除算:t=c*c+d*d,(a+bi)/(c+di)=(ac+bd)/t+(bc-ad)/ti
次にa 0~anを深く検索し、aiを減算するたびにbを除いた後、残りは0まで定数がある.除法の場合、整除(上のac+bdとbc-adがtの倍数)を保証するため、多くの時間を減らすことができます
コードは次のとおりです.
1 #include <stdio.h>
2 typedef __int64 LL;
3 LL xr, xi, br, bi, sq, ans[101];
4 int flag, k;
5 //--------- ----------
6 void dfs(int step, LL real, LL com){
7 LL tx, ty;
8 if (step > 100 || flag) return;
9 if (!real && !com){
10 flag = 1;
11 k = step;
12 return;
13 }
14 // --t=c*c+d*d, (a+bi)/(c+di)=(ac+bd)/t+(bc-ad)/ti----
15 for (int i = 0; i*i < sq; i++){
16 tx = (real - i)*br + com*bi;
17 ty = -(real - i)*bi + com*br;
18 ans[step] = i;
19 if (!(tx%sq) && !(ty%sq))
20 dfs(step + 1, tx / sq, ty / sq);
21 if (flag) return;
22 }
23 }
24 int main(){
25 int i, t;
26 scanf("%d", &t);
27 while (t--){
28 flag = 0;
29 scanf("%I64d%I64d%I64d%I64d", &xr, &xi, &br, &bi);
30 sq = br*br + bi*bi;
31 dfs(0, xr, xi);
32 if (!flag)
33 printf("The code cannot be decrypted.
");
34 else{
35 printf("%d", ans[k - 1]);
36 for (i = k - 2; i >= 0; i--)
37 printf(",%I64d", ans[i]);
38 printf("
");
39 }
40 }
41 return 0;
42 }View Code