求和B

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 sumb.in 输出文件 sumb.out

【问题描述

正如本题标题所言,你的任务是计算一些整数的和,真的很简单,对吧?错,实际并非如此,因为这里面有很多跟普通的加法不同的地方,比如操作符、操作数啦等等。请仔细阅读下面的细节:
首先,你要抛开普通的加法规则,来进行不带进位的加法运算,那意味着我们必须依照普通加法规则把两个整数相加,但是要忽略掉每一个地方的进位。举个例子,假如我们要把十进制的 55 和 76 相加,使用普通的加法规则得到的结果为 131 ;然而使用“不带进位的加法”规则所得到的结果为 21 ,两种运算的过程如下图 1.2.1 和 1.2.2 所示。
 
   
5
5
 
5
5 
           
+  
7
6
+
7
6
             
-------------------------------  --------  ------- ------                     
    1 1      1                          
+ 1 2    +  2                            
--------------------------------  --------  ------- ------                    
  1 3 1    2  1                          
1.2.1 Usual Addition Figure 1.2.2 No Carry Addition
其次,这种加法可以在 2 到 16 的任一种进制下运行,举例来说,给定两个十进制数 55 和 76 ,如果我们在十进制下进行这种不带进位的加法运算,他们的和为( 21 ) 10 ,而在二进制下, 55 和 76 的二进制数分别表示为( 110111 ) 2 和( 1001100 ) 2 ,它们的和将为( 1111011 ) 2 = ( 123 ) 10 。
最后一点,给定的操作数不是单一的整数,而是一个整数段,正如我们所知,整数段 [x,y] 表示从 x 开始,以 y 结束的连续的整数,两个整数段 [x1,y1] 、 [x2,y2] 的和等于每一个整数段中所有的整数的和。(如果一个整数在两个段里均存在,它将被计算两次。)
现在我们可以结束这个问题的阐述了:给定一些基于 2 到 16 进制的整数段,你的任务是依照无进位的加法规则计算它们的和。
【输入格式】
输入文件包含若干个测试数据,第一行是一个整数 T(1 ≤ T ≤ 20) ,表示下面有 T 组测试数据,对于每一组测试数据,第一行有两个整数, N 和 M , (1 ≤ N ≤ 100 , 2 ≤ M ≤ 16) , N 表示整数段的个数, M 表示所求的和的进制数,接下来有 N 行,每一行包含两个 32 位无符号位的整数, x 和 y ,表示整数段 [x,y] ( x,y 均为十进制数,且 x ≤ y )。
【输出格式】
对于每一组测试数据,输出只有一行,包含一个 32 位无符号位的整数,为计算结果的十进制表示。
 
【输入样例】
sumb.in
3
2 10
55 55
76 76
2 2
55 55
76 76
3 2
0 3
8 15
4 7
sumb.out
21
123
0