首页 > ACM题库 > HDU-杭电 > hdu 1930 And Now, a Remainder from Our Sponsor-数论-[解题报告]C++
2013
12-26

hdu 1930 And Now, a Remainder from Our Sponsor-数论-[解题报告]C++

And Now, a Remainder from Our Sponsor

问题描述 :

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

输入:

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.

输出:

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.

样例输入:

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

样例输出:

THE CAT IN THE HAT
THE END

/**
* url : http://acm.hdu.edu.cn/showproblem.php?pid=1930
* stratege : 解一元线性同余方程组, 扩展欧几里得
* Author: johnsondu
* Status: johnsondu 0MS 284K 2207B C++ 2012-08-19 13:13:15 
* Trick: There will be no blank in the end of the text 
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <string>
#include <iomanip>
using namespace std;

const int N = 2005 ;
int key[N], num, n ;
int str[N] ;
int res[N] ;
int r[N] ; 

void input ()
{
    int i ;
    scanf  ("%d", &n) ;
	memset (res, 0, sizeof (res)) ;
	memset (str, 0, sizeof (str)) ;
	memset (r, 0, sizeof (r)) ;
	memset (key, 0, sizeof (key)) ;
	num = 0 ;
    for (i = 0; i < 4; i ++)  // key
        scanf ("%d", &key[i]) ;
    for (i = 0; i < n; i ++)  // the set of remainder
        scanf ("%d", &str[i]) ;
	
	
}

void exGcd (int a, int b, int &d, int &x, int &y)  // Extended_Euclid
{
    if (b == 0)
    {
        d = a ;
        x = 1 ;
        y = 0 ;
        return ;
    }
    exGcd (b, a%b, d, x, y) ;
    int tmp = x ;
    x = y ;
    y = tmp - (a/b)*y ;
}

void getNum ()
{
    int i, j ;
    int a, b, c, d, x, y ;
    for (i = 0; i < n; i ++)
    {
        r[3] = str[i] % 100 ;        //transform the set of remainder into the 
        r[2] = (str[i]%10000)/100 ;  //single remainder of the key
        r[1] = (str[i]%1000000)/ 10000 ;
        r[0] = str[i]/1000000; 

		int ta = key[0] ;
		int tr = r[0] ;
									//mission: x = r1 (mod a1), x = r2 (mod a2), ..., find x ;
        for (j = 1; j < 4; j ++)    //a1, a2, ... are key[i], r1, r2, ... are r[i] 
        {							//find the str[i]'s value 
            a = ta, b = key[j] ;
			c = r[j] - tr ;
            exGcd (a, b, d, x, y) ;
			
			int t = b/d ;
			x = (x*(c/d)%t + t) % t ;
			tr = ta*x + tr ;
			ta = ta * (key[j]/d) ;
        }
        res[i] = tr ;
    }
}

void output ()
{
	int i ;
	int a, b, c ;
	char destr [10005] ;
	int len = 0 ;
	for (i = 0; i < n; i ++)
	{
		a = res[i] / 10000 ;
		b = (res[i] % 10000) / 100 ;
		c = res[i] % 100 ;
		
		if (a != 27)
			destr[len++] = 'A' + a - 1 ;
		else destr[len++] = ' ' ;
		if (b != 27)
			destr[len++] = 'A' + b - 1 ;
		else destr[len ++] = ' ' ;
		if (c != 27)
			destr[len++] = 'A' + c - 1 ;
		else destr[len ++] = ' ' ;
	}
	while (destr[len-1] == ' ')  //ignore the blank in the end of text.
	{
		len -- ;
	}
	for (i = 0; i < len; i ++)
		printf ("%c", destr[i]) ;
	printf ("\n") ;
}

int main ()
{
    int tcase ;
    scanf ("%d", &tcase)  ;
    while (tcase --)
    {
        input () ;
        getNum () ;
		output () ;
    }
    return 0 ;
}

解题转自:http://blog.csdn.net/zone_programming/article/details/7882963


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮