Level 1: Addition, subtraction, multiplication and division of large integers
Task description
The task of this level: Master the basic idea of large integers, and use the basic operations of large integers to calculate the factorial of a conventional integer n, and then count the number of digits 0 in the large integer n!.
Related knowledge
In order to complete this task, you need to master: 1. The idea of large integers, 2. Addition of large integers, 3. Subtraction of large integers, 4. Multiplication of large integers and integers, 5. Multiplication of large integers, 6. Large integers and integers Division, 7.n factorial solution ideas.
The idea of large integers
The idea of large integers: use arrays to store large integers (ultra-long integers). For the sake of simplicity, it is agreed that each array element stores a number fragment with the same number of digits (T bits) (assuming T = 4 bits).
Set an integer array a[0,1,..,N?1] of size N. Given a large integer 998877665544332211, each array unit uses T=4 bits to store. In order to facilitate calculation, the large integer is The low bits are stored in the high-dimensional index of the array, as shown in the figure below:
In the code file, the char_to_int function has realized the conversion of the large integer string sequence s to the integer array c. The initialization of c is all 0, and then starting from the subscript (N? 1) from the right Store large integers to the left, and each array unit stores T=4 digits, corresponding to the result in the base system K=10T=10000.
In addition, the output function has implemented the output of integer arrays. The basic idea is that from left to right, the first array unit that is not 0 is the head of a large integer, and then each array unit is Output T = 4 digits (note the complement of 0s).
Large Integer Addition
The addition of large integers is similar to the general addition of integers. Starting from the low-order bit, the numbers in the same position are added. If it is greater than the base K=10000, then carry is carried out, and so on. In particular, when the base K=10, the number stored in each array unit is T=1 digit. The addition of large integers is equivalent to the addition of regular integers, except that an array is used to simulate the calculation process.
For example, two large integers are 998877665544332211 and 112233445566778899. According to the parameter settings of T=4 and K=10000, they are stored in integer arrays a and b respectively. The size of the arrays is N. Their addition operation (c=a + b) The process is as shown in the figure:
Subtraction of large integers
Similarly, the subtraction process of large integers is similar to that of general integer subtraction. Starting from the low bit, the numbers in the same position are subtracted. When the minuend is smaller than the minuend, the minuend borrows 1 from the high bit. When T=4,K =10000, borrowing one bit is equivalent to adding 10000. In particular, if the integer being decremented is smaller than the large integer of the subtrahend, they are swapped first, then subtracted, and finally a negative sign is added to the result. For convenience, the test data of this level ensures that the minuend is greater than the minuend.
For the above large integer a=998877665544332211 and large integer b=112233445566778899, their subtraction operation (c=a?b) process is shown in the figure below:
Multiplication of large integers and integers
We know that multiplication between integers is to multiply them bit by bit and then add them. For the multiplication between large integers and integers, the “bits” are expanded into “blocks”, that is, each array unit of the large integer is multiplied by the integer respectively, and then a carry (initially 0) is added, and the result is Put it in the corresponding position, if it exceeds the base K, then carry, and so on.
For example, the large integer 123456789 and the integer 12345 are set according to the parameters of T=4, K=10000. The large integer is stored in the integer array d, the array size is N, and the integer is stored in the integer variable p. Their multiplication operation ( c=d×p) process is shown in the figure:
Large Integer Multiplication
We already know the multiplication operation between large integers and integers. The multiplication operation between large integers a and large integers b is an extension of the multiplication operation between large integers and integers. That is to say, the multiplication operation between large integers a and large integers b is Each array element is multiplied, placed at the corresponding location, and the carries are accumulated.
For the above large integer a=998877665544332211 and large integer b=112233445566778899, their multiplication operation (c=a×b) process is as shown in the figure below:
Division of large integers and integers
The division operation of a large integer d and an integer p preserves the quotient and the remainder. The quotient may still be a large integer, and the remainder is an integer smaller than the divisor. The large integer is used as the dividend. Starting from the high bit, divide each array unit d[i] by the divisor p in sequence (from left to right i=0→N?1). The current integer division result is stored as the quotient in the high bit c corresponding to the array c. In [i], the remainder is retained in the calculation of the next array unit, and so on. The final remainder is the remainder after the large integer is divided.
For the above large integer d=123456789 and integer p=12345, their division operation (c=d/p, r=d process is shown in the figure below:
n‘s factorial solution
The factorial of n is a very large integer. First, you need to use the basic arithmetic rules of large integers to find the value of n!. This step can use the multiplication operation of large integers and integers, and then loop n? 1 times of multiplication to get n!.
n!=1×2×3×..×n
The second step is to count the number of digits 0 in n!. Because large integers are stored in blocks in the array, there are two statistical methods (note n!=M):
-
Use the division operation of large integers and integers: divide M by 10, and determine whether the remainder r is 0. If r=0, the answer is accumulated by 1, and then assign M to the quotient c, that is, M=c, and repeat the above steps. Until M=0, the program ends;
-
With the help of the block storage method of large integers in the array: loop through the array units of large integers n!, calculate the number of integers in each unit that contain the number 0, and finally perform the cumulative sum to get the answer. Note that the value in each integer unit is not necessarily T=4 digits, for example, M[i]=102. When i is not the head of a large integer, the real data of M[i] is 0102, including two numbers 0 ( A simple processing technique: add M[i] plus K=10000, that is, M[i] + K=10102, and then determine the number of 0s it contains).
Programming Requirements
The programming task of this level is to complete the code between Begin and End in the code snippet calc on the right. The specific requirements are as follows:
- In
calc, based on the basic operation principles of large integers, the factorial of the integernis calculated, and the number0 in, and then use the statistical results as the function return value.n!is calculated.
Test Instructions
The platform will automatically compile the completed code and generate several sets of test data. Then it will judge whether the program is correct based on the output of the program. The test data guarantees 10001>n>0.
The following are test samples for the platform:
Test input: 10 Expected output: 2
Input format: Line 1: Integer n Output format: Line 1: Number of digits 0 in n!
Tips: Pay attention to the situation when integer multiplication goes out of bounds
//
// main.cpp
// step1
//
// Created by ljpc on 2018/12/4.
// Copyright ? 2018 ljpc. All rights reserved.
//
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
//Maximum length N, block length K
const int N = 10001;
const int K = 10000;
const int T = (int)log10(K); // K=10000, T=4
void char_to_int(char *s, int *c)
{
// *s = 1234567890
// *c = 0000 .... 0012 3456 7890 (K=10000, T=4, c[0] c[1] .... c[N-2] c[N-1])
// i = 0 N-3 N-2 N-1 (subscript index i of c)
int L = (int)strlen(s);
for (int i=N-1; i>=0; i--) {
c[i] = 0;
if (L>=0) {
for (int j=0; j<T; j + + ) {
if (L-T + j < 0) {
continue;
}
c[i] = c[i] * 10 + s[L-T + j] - '0';
}
L -= T;
}
}
}
void output(int *c)
{
// *c = 0000 .... 0012 3456 7890 (K=10000, T=4, c[0] c[1] .... c[N-2] c[N-1])
// i = 0 N-3 N-2 N-1 (subscript index i of c)
// out= 1234567890
bool flag = true;
for (int i=0; i<N; i + + ) {
if (flag & amp; & amp; c[i]==0) {
continue;
}
if (flag) { // The first non-zero number: the header block of large numbers
printf("%d", c[i]);
flag = false;
}
else { // T number block after the big number header block
int TK = K/10;
int tmp = c[i];
while (TK) {
printf("%d", tmp/TK);
tmp %= TK;
TK /= 10;
}
}
}
printf("\
");
}
void add(int *a, int *b, int *c)
{
int carry = 0;
for (int i=N-1; i>=0; i--) {
c[i] = 0;
c[i] = a[i] + b[i] + carry;
carry = c[i] / K;
c[i] = c[i] % K;
}
}
void sub(int *a, int *b, int *c)
{
int borrow = 0;
for (int i=N-1; i>=0; i--) {
c[i] = 0;
c[i] = a[i] - b[i] - borrow;
if (c[i] >= 0) {
borrow = 0;
}
else {
c[i] = c[i] + K;
borrow = 1;
}
}
}
void mul1(int *a, int b, int *c)
{
long long tmp = 0;
int carry = 0;
for (int i=N-1; i>=0; i--) {
tmp = (long long)a[i] * (long long)b + (long long)carry;
c[i] = (int)(tmp % K);
carry = (int)(tmp / K);
}
}
void mul2(int *a, int *b, int *c)
{
long long tmp = 0;
int carry = 0;
for (int i=N-1; i>=0; i--) {
c[i] = 0;
}
for (int i=N-1; i>=0; i--) { // b[i]
carry = 0;
for (int j=N-1, idc=i; j>=0 & amp; & amp;idc>=0; j--, idc--) { // a[j]
tmp = (long long)a[j] * (long long)b[i] + (long long)carry + (long long)c[idc];
c[idc] = (int)(tmp % K);
carry = (int)(tmp / K);
}
}
}
int div(int *a, int b, int *c)
{
long long tmp = 0;
int remain = 0;
for (int i=0; i<N; i + + ) {
tmp = (long long)a[i] + (long long)remain * (long long)K;
c[i] = (int)(tmp / b);
remain = (int)(tmp % b);
}
return remain;
}
int calc(int n)
{
// Please add code here to complete this task
/********* Begin *********/
int a[N]={0};
int c[N]={0};
a[N-1]=1;
for(int i=2; i<=n; i + + ){
mul1(a,i,c);
for(int j=0; j<N; j + + ){
a[j]=c[j];
c[j]=0;
}
}
int tot=0;
while(1){
bool flag=true;
for(int i=0; i<N; i + + ){
if(a[i]){
flag=false;
break;
}
}
if (flag) {
break;
}
int r=div(a,10,c);
if (r==0) {
tot + + ;
}
for(int j=0; j<N; j + + ){
a[j]=c[j];
c[j]=0;
}
}
return tot;
/********* End *********/
}
int main(int argc, const char * argv[]) {
int n;
scanf("%d", & amp;n);
int tot = calc(n);
printf("%d\
", tot);
return 0;
}