[sicily] 1020. Big Integer

短命女 2022-07-24 04:15 153阅读 0赞

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,b2,...,bn, 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,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] != '\0'; 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] = {
       '\0'};
    
        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;
    }