问题 B: Casting

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

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,

782910 mod 9 = 8

377777777777777738 mod 7 = 6

1234567 mod 6 = 3

(Note that 377777777777777738 = 112589990684261910 and 1234567 = 2287510.)

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.

输入

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of 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.

输出

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 − l).

样例输入

5

1 10 7829

2 7 123456

3 6 432504023545112

4 8 37777777777777773

5 2 10110100010101010101101110001010001010101010101010111

样例输出

1 8

2 3

3 1

4 6

5 0

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int maxn = 1e7+10;
char s[maxn];
int main()
{
    int t;
    scanf ("%d",&t);
    while (t--) {
        int id,b;
        scanf ("%d%d ",&id,&b);
        int ans=0,mod=b-1;
        scanf ("%s",s);
        if(b==2) {
            printf ("%d 0\n",id);
            continue;
        }
        int l=strlen (s);
        for(int i=0;i<l;i++) {
            ans=ans+s[i]-'0';
            ans%=mod;
        }
        printf ("%d %d\n",id,ans%mod);
    }
    return 0;
}