How can I scan a number having upto 10^18 digits in C

Question

No data type can store such large number. Using array int a[pow(10,pow(10,18))] again won't do the job because pow() returns double and double can't store 10^(10^18).

Anyone having any idea?

I'm trying to solve the following problem:

Consider an integer with N digits (in decimal notation, without leading zeroes) D₁,D₂,D₃,…,D_N. Here, D₁ is the most significant digit and D_N the least significant. The weight of this integer is defined as:

∑ i=2 -> N (D_i−D_i−1).

You are given integers N and W. Find the number of positive integers with N digits (without leading zeroes) and weight equal to W. Compute this number modulo 10⁹+7.

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. The first and only line of each test case contains two space-separated integers N and W denoting the number of digits and the required weight.

Output:

For each test case, print a single line containing one integer — the number of N-digit positive integers with weight W, modulo 10⁹+7.

Constraints:

• 1≤T≤10⁵
• 2≤N≤10¹⁸
• |W|≤300

Answer 1

You don't need to store a number with 10^18 digits. Look at the definition of the weight:

∑ i=2 -> N (D_i−D_i−1)

Each element in the sum is the difference of two consecutive digits.

Let's take for example a 4 digit number whose digits are D₁, D₂, D₃, D₄. Then the sum is:

(D₂ - D₁) + (D₃ - D₂) + (D₄ - D₃)

Reording the operands:

D₄ - D₃ + D₃ - D₂ + D₂ - D₁

You'll see that all but the first and last digits cancel out! So the whole sum is D₄ - D₁. In fact, for any number of digits N, the sum is:

D_N - D₁

So only the first and the last digits are relevant. You should be able to figure out the rest from there.

Answer 2

There are libraries for handling these sorts of problems, like The GNU Multiple Precision Arithmetic Library:

What is GMP?

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

The main target applications for GMP are cryptography applications and research, Internet security applications, algebra systems, computational algebra research, etc.

But 10^18 would take a huge (and effectively impossible) amount of memory (if my math is correct: 2.881 EiB).

Answer 3

The referenced problem takes input from 2 ≤ N ≤ 10^18. That isn't 10^18 digits (or 10^10^18 which is absurdly enormous) but 18 digits or 2 to 1,000,000,000,000,000,000. This will fit inside a 64 bit integer, signed or unsigned.

Use int64_t from stdint.h.

10^18 is pushing the limits of 64 bit integers, probably why they chose it. Anything larger should use an arbitrary precision math library such as GMP.

...but there are limits. Simply storing such a number would take about 1 million gigabytes. So while the problem is about solving for numbers with 10^18 digits, I strongly suspect you're not supposed to solve it by actually storing those numbers. There's some mathematical technique you're supposed to apply.