B-Casting

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 449 Accepted Submission(s): 223

Problem Description

Casting around for problems leads us to combine modular arithmetic with different integer bases, particularly the problem of computing values modulo b-1, where b is the base in which the value is represented. For example,

7829
₁₀ mod 9 = 8,

37777777777777773
₈ mod 7 = 6

123456
₇ mod 6 = 3

(Note that 37777777777777773
₈ = 1125899906842619
₁₀ and 123456
₇ = 22875
₁₀.)

Your job is to write a program that reads integer values in various bases and computes the remainder after dividing these values by one less than the input base.

Input

The first line of input contains a single integer P, (1 <= P <= 1000) , which is the number o data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input containing three space-separated values. The first is an integer which is the data set number. The second is an integer which is the number, B (2 <= B <= 10), denoting a numeric base. The third is an unsigned number, D, in base B representation. For this problem, the number of numeric characters in D will be limited to 10,000,000.

Output

For each data set there is a single line of output. It contains the data set number followed by a single space which is then followed by the remainder resulting from dividing D by (B-1).

Sample Input

4
1 10 7829
2 7 123456
3 6 432504023545112
4 8 37777777777777773

Sample Output

1 8
2 3
3 1
4 6

这题没啥好说的，水题，用字符串保存那个数，然后把它转化成十进制再mod给的那个值，由于这个数太大所以每计算一步就要mod一下，这样就没问题了

#include<stdio.h>

#include<string.h>

char s[10000005];

int main()

{

	int i,j,n,x,t;

	__int64 sum;

	scanf("%d",&n);

	while(n--)

	{

		scanf("%d%d%s",&t,&x,s);

		j=strlen(s);

		for(i=0,sum=0;i<j;i++)

		{

			sum=(sum*x+s[i]-'0')%(x-1);//每次计算都mod(x-1)

		}

		printf("%d %I64d\n",t,sum);

	}

	return 0;

}

上面那个好理解，但是跑了1000多ms，内存7000多k，再贴一个跑到前几名的代码，234ms，220k

#include<stdio.h>

#include<string.h>

int main()

{

	int n,x,t;

	int sum;

	char c;

	scanf("%d",&n);

	while(n--)

	{

		scanf("%d%d",&t,&x);

		getchar();

		sum=0;

		while((c=getchar())!='\n')//这里没存那个数

		{

			sum=(sum*x+c-'0');

			if(sum>1000000)

				sum%=(x-1);

		}

		printf("%d %d\n",t,sum%(x-1));

	}

	return 0;

}

巴特西

hdu4485 B-Casting(mod运算)

B-Casting

最新文章

热门文章