[sicily] 1020. Big Integer

1020. Big Integer

Constraints

Time Limit: 1 secs,Memory Limit: 32 MB

Description

Long long ago,there was a super computer that could deal with VeryLongIntegers(no VeryLongInteger will be negative). Do you know how this computer stores the VeryLongIntegers? This computer has a set of n positive integers: b1,b2,...,bn,which is called a basis for the computer.

The basis satisfies two properties:
1) 1 < bi <= 1000 (1 <= i <= n),2) gcd(bi,bj) = 1 (1 <= i,j <= n,i ≠ j).

Let M = b1*b2*...*bn

Given an integer x,which is nonegative and less than M,the ordered n-tuples (x mod b1,x mod b2,x mod bn),which is called the representation of x,will be put into the computer.

Input

The input consists of T test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains three lines.
The first line contains an integer n(<=100).
The second line contains n integers: b1,which is the basis of the computer.
The third line contains a single VeryLongInteger x.

Each VeryLongInteger will be 400 or fewer characters in length,and will only contain digits (no VeryLongInteger will be negative).

Output

For each test case,print exactly one line -- the representation of x.
The output format is:(r1,r2,rn)

Sample Input

2

3
2 3 5
10

4
2 3 5 7
13

Sample Output

(0,1,0)
(1,3,6)

解题思路：使用到了大数取余的方法

1 % m = 1
12 % m = (1 * 10 + 2) % m = (1 % m * 10 + 2) % m
123 % m = (12 * 10 + 3) % m = (12 % m * 10 + 3) % m
1234567890123456789 % m = ((1 % m * 10 + 2) % m * 10 + 3) % m * 10….

#include <iostream>
using namespace std;

int Mod(char x[401],int b)
{
  int a = 0;
  for (size_t i = 0; x[i] != ''; i++) {
    a = (a * 10 + (x[i] - '0')) % b;
  }
  return a;
}

int main(int argc,char const *argv[])
{
  int t;
  cin >> t;
  while (t--)
  {
    int basis[101]= {0},result[101] = {0};
    char x[401] = {''};

    int n;
    cin >> n;
    for (size_t i = 0; i < n; i++) {
      cin >> basis[i];
    }

    cin >> x;
    cout << "(";
    for (size_t i = 0; i < n - 1; i++) {
      cout << Mod(x,basis[i]) << ",";
    }
    cout << Mod(x,basis[n-1]) << ")" << endl;

  }
  return 0;
}