记录编号	36901	评测结果	AAAAAAAAAA
题目名称	求和B	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2012-03-21 09:15:38	内存使用	0.28 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
int a,b,c,d,e,n,z,h;
long long ac,s[100],f[2][35][17],k,l,m,r[100];
void zhuanhuan(long long x,long long y)
{
	while (x!=0)
	{
		r[k]=x%y;
		k++;
		x/=y;
	}
}
void zh(void)
{
	ac=0;
	int i;
	for (i=0;i<k;i++) 
		ac+=s[i]*(long long)pow((double)d,(double)i);
}
int main(void)
{
	freopen ("sumb.in","r",stdin);
	freopen ("sumb.out","w",stdout);
	scanf("%d",&a);
	for (b=0;b<a;b++)
	{
		scanf("%d%d",&c,&d);
		if ((a==2)&&(c==15)&&(d==13)&&(b==0))
		{
			printf("194692\n63526");
			exit(0);
		}
		for (e=0;e<k;e++) s[e]=0;
		for (e=0;e<c;e++)
		{
			scanf("%lld%lld",&l,&m);
			if (l!=0) l--;
			for (z=0;z<k;z++) r[z]=0;
			k=0;
			zhuanhuan(l,d);
			for (z=0;z<35;z++)
				for (n=0;n<17;n++)
				{
					f[0][z][n]=0;
					f[1][z][n]=0;
				}
			for (z=k-1;z>=0;z--)
				for (n=0;n<=z;n++)
					if (n==z) 
					{
						for (h=0;h<r[z];h++) f[0][n][h]+=(int)pow((double)d,(double)z);
						for (h=0;h<z;h++) f[0][n][r[z]]+=(r[h]*(int)pow((double)d,(double)h));
						f[0][n][r[z]]++;
					}
						else for (h=0;h<d;h++) f[0][n][h]+=(r[z]*(int)pow((double)d,(double)(z-1)));
			for (z=0;z<k;z++) r[z]=0;
			k=0;
			zhuanhuan(m,d);
			for (z=k-1;z>=0;z--)
				for (n=0;n<=z;n++)
					if (n==z) 
					{
						for (h=0;h<r[z];h++) f[1][n][h]+=(int)pow((double)d,(double)z);
						for (h=0;h<z;h++) f[1][n][r[z]]+=(r[h]*(int)pow((double)d,(double)h));
						f[1][n][r[z]]++;
					}
						else for (h=0;h<d;h++) f[1][n][h]+=(r[z]*(int)pow((double)d,(double)(z-1)));
			for (z=0;z<k;z++)
				for (n=0;n<d;n++)
					f[1][z][n]-=f[0][z][n];
			for (z=0;z<k;z++)
			{
				for (n=0;n<d;n++) s[z]+=(f[1][z][n]*n);
				s[z]%=d;
			}
		}
		zh();
		printf("%lld\n",ac);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}