Description

IBM has decided that all messages sent to and from teams competing in the ACM programming contest should be encoded. They have decided that instead of sending the letters of a message, they will transmit their remainders relative to some secret keys which are four, two-digit integers that are pairwise relatively prime. For example, consider the message "THE CAT IN THE HAT". The letters of this message are first converted into numeric equivalents, where A=01, B=02, …, Z=26 and a blank=27. Each group of 3 letters is then combined to create a 6 digit number. (If the last group does not contain 3 letters it is padded on the right with blanks and then transformed into a 6 digit number.) For example
THE CAT IN THE HAT → 200805 270301 202709 142720 080527 080120
Each six-digit integer is then encoded by replacing it with the remainders modulo the secret keys as follows: Each remainder should be padded with leading 0’s, if necessary, to make it two digits long. After this, the remainders are concatenated together and then any leading 0’s are removed. For example, if the secret keys are 34, 81, 65, and 43, then the first integer 200805 would have remainders 1, 6, 20 and 38. Following the rules above, these combine to get the encoding 1062038. The entire sample message above would be encoded as
1062038 1043103 1473907 22794503 15135731 16114011

 
Input

The input consists of multiple test cases. The first line of input consists of a single positive integer n indicating the number of test cases. The next 2n lines of the input consist of the test cases. The first line of each test case contains a positive integer (< 50) giving the number of groups in the encoded message. The second line of each test case consists of the four keys followed by the encoded message.
Each message group is separated with a space.

 
Output

For each test case write the decoded message. You should not print any trailing blanks.
 
Sample Input

2
6
34 81 65 43 1062038 1043103 1473907 22794503 15135731 16114011
3
20 31 53 39 5184133 14080210 7090922
Sample Output

THE CAT IN THE HAT
THE END


解题报告:这道题就是规律题,题意就是给我们4个数之后,再给出若干个七位或八位的数,先把这个数分成四个两位的数,再找到一个数能取模后的余数正好等于分成的四个数,这个数就是所求的目标数,再根据规则变换即可!注意如最后有空格的话,不输出!


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[5], b[5], c[5];
int main()
{
    int t, n, i, j, p, q;
    scanf("%d", &t);
    while (t –)
    {
        scanf("%d", &n);
        for (i = 1; i <= 4; ++i)
        {
            scanf("%d", &a[i]);
        }
        for (i = 1; i <= n; ++i)
        {
            scanf("%d", &p);
            for (j = 4; j >= 0; –j)//把所给的七位或八位数分割成四个两位数
            {
                b[j] = p % 100;
                p = p /100;
            }
            int len = 272727/a[1];
            for (j = 1; j <= len; ++j)//找到一个数能取模后等于分割后的四个数
            {
                q = j * a[1] + b[1];
                if (q % a[2] == b[2] && q % a[3] == b[3] && q % a[4] == b[4])
                {
                    break;
                }
            }
            for (j = 3; j >= 0 ;–j)//把这个六位数分成三个两位的数
            {
                c[j] = q % 100;
                q = q / 100;
            }
            for (j = 1; j <= 3; ++j)
            {
                if (c[j] == 27 && i != n)//若最后有空格,不输出
                {
                    printf(" ");
                }
                else if (c[j] >= 1 && c[j] <= 26)
                {
                    printf("%c", c[j] + 'A' – 1);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

——————————–

这里只将题意,解密的过程是将每个数分解成4个数,与一开始输入的四个数组成同余方程组,求解可得原密码3个字符对应的6位数,翻译回来即可,不过注意每个句子后面不应该有多余的空格,字符数组记得开够,不然wa
#include<stdio.h>
#include<math.h>
#include<string.h>
 
__int64 a[4];
char ans[100001];
 
int s_i;
 
 
__int64 extended_euclid(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    __int64 d = extended_euclid(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
 
 
__int64 chinese_remainder(__int64 b[], __int64 r[], int n)//b 表示除数,r 表示对应的余数
{
    int i, j;
    __int64 M = b[0], R = r[0], x, y, d;
 
    for(i = 1; i < n; i++)
    {
        d = extended_euclid(M, b[i], x, y);
 
        // 合并俩个方程
        //1)X mod M=R
        //2)X mod b[i] = r[i]
        //根据上面的说法,先转化为 M * x + b[i] * y =r[i]-R , 根据(r[i]-R)% gcd(M,b[i])判断是//否有解
 
        if((r[i] – R) % d)
            return 0;
 
        //有解,那么此时的x 为M 的系数,也就是说合并俩个方程之后求出的
        x = (r[i] – R) / d * x % (b[i] / d);//原来方程对应的系数
 
        R += x * M;//此时的R表示合并俩个方程之后代表的X
        M = M * b[i] / d;//更新合并之后的方程
        R %= M;
    }
    return R = R > 0 ? R : R + M;
}
 
 
void change(int num)
{
    int i;
    __int64 b[4], key;
    for( i = 0 ; i < 4 ; i++)
    {
        b[3 – i] = num % 100;
        num /= 100;
    }
 
    key = chinese_remainder(a, b, 4);
 
    for( i = 0 ; i < 3 ; i++)
    {
        if( (key % 100) > 26)
            ans[s_i + 2 – i] = ' ';
        else
            ans[s_i + 2 – i] = 'A' + (key % 100 – 1);
        key /= 100;
    }
    s_i += 3;
}
 
int main()
{
    int T, i, j, n, num;
    scanf("%d", &T);
 
    while(T–)
    {
        scanf("%d", &n);
        memset(ans, 0, sizeof(ans));
        for( i = 0 ; i < 4; i++)
            scanf("%d", &a[i]);
 
        s_i = 0;
 
        for( i = 0 ; i < n ; i++)
        {
            scanf("%d", &num);
 
            change(num);
        }
        s_i–;
        while( ans[s_i] == ' ')
            s_i–;
        s_i++;
        ans[s_i] = '\0';
        printf("%s\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation