Description

related problem: 11112-Big Number

Hey, do you want to hear something amazing? Square of a 16-digit integer can be larger that the maximum of long long int.

Given a 16-digit integer n with no trailing zeros, please output the result of n*n.

Hint and Suggested Implementation

How to represent an integer that is too long to be stored in either int or long long int?

A simple and intuitive method is to use a string ( char array ). Addition and Multiplication can be implemented using 直式 , for example :

Another method is to use an int array. An integer can be sliced up to several 4-digit numbers, with each of them stored in array. Addition and Multiplication can be implemented using 直式 as well, for example :

From another point of view, the first method (using char array) is to implement big number multiplication under base 10 system, while the second method (using int array, with each array element storing a 4-digit number) is to implement big number multiplication under base 10000 multiplication.

Below is a suggested way to implement big number multiplication using the second method. For this problem, you can either fill in the ??? in the code below, or feel free to write your own version of big number multiplication.

x
1
#include <stdio.h>
2
#define BIGINT_WIDTH 4
3
#define BIGINT_BASE 10000
4
#define DIGIT_NUM 16
5
#define NUM_SIZE (DIGIT_NUM/BIGINT_WIDTH)
6
#define ANS_SIZE (NUM_SIZE*2)
7
​
8
int main()
9
{
10
    int num[NUM_SIZE] = {0}; // store input number (under base 10000)
11
    int ans[ANS_SIZE] = {0}; // store answer (under base 10000)
12
    char input[DIGIT_NUM];   // store input nunber (under base 10)
13
    
14
    // input : input 16-digit number to a char array (under base 10)
15
    for(int i = 0; i < DIGIT_NUM; i++) scanf("%c", &input[i]);
16
​
17
    // convert from base 10 to base 10000
18
    for(int d = 0; d < DIGIT_NUM; d++)
19
    {
20
        int num_idx = (DIGIT_NUM-d-1)/BIGINT_WIDTH;
21
        num[num_idx] *= 10;
22
        num[num_idx] += input[d]-'0';
23
    }
24
​
25
    // TODO: multiplication
26
    for(int up = 0; up < NUM_SIZE; up++)
27
        for(int down = 0; down < NUM_SIZE; down++)
28
            ans[???] += num[???]*num[???];
29
​
30
    // TODO: deal with carry (處理進位)
31
    for(int d = 0; d < ANS_SIZE-1; d++)
32
    {
33
        ???
34
    }
35
​
36
    // print answer
37
    printf("%4d", ans[ANS_SIZE-1]);
38
    for(int d = ANS_SIZE-2; d >= 0; d--) printf("%04d", ans[d]);
39
    printf("\n");
40
​
41
    return 0;
42
}
43
​

Input

A 16-digit integer n with no trailing zeros. In other words, (10^15) <= n <= (10^16)-1.

Output

The result of n*n. There should be a new line character in the end, and the output format is always 32-digit wide with space prepended if needed.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss