LQ0262 棋盘放麦子【大数+亿进制】

题目来源：蓝桥杯2012初赛 Java C组C题

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

你一定听说过这个故事。国王对发明国际象棋的大臣很佩服，问他要什么报酬，大臣说：请在第 11 个棋盘格放 1 粒麦子，在第 2 个棋盘格放 2 粒麦子，在第 3 个棋盘格放 4 粒麦子，在第 4 个棋盘格放 8 粒麦子，…后一格的数字是前一格的两倍，直到放完所有棋盘格（国际象棋共有 64 格）。

国王以为他只是想要一袋麦子而已，哈哈大笑。

当时的条件下无法准确计算，但估算结果令人吃惊：即使全世界都铺满麦子也不够用！

请你借助计算机准确地计算，到底需要多少粒麦子。

问题分析
这是一个大数计算问题。
用Python语言来实现比较简单，因为有大数类型及运算符。
用Java语言来实现也比较简单，可以用大数来实现，不过也许迭代计算会比较快一些。
用C语言来实现，则需要模拟大数计算，这里采用亿进制来实现。采用迭代计算，计算2ⁿ(n=1,2,3,…,64)时，可以避免重复计算。
不做乘法计算或计算结果不大的情况下，还可以使用兆进制。
更简单的方法是使用unsigned long long类型，并使用迭代计算，。
还有更快更简单的计算，因为
麦粒数=1+2+4+…+2⁶³=2⁶⁴-1=64位二进制的1。

AC的C语言程序（二进制位）如下：

/* LQ0262 棋盘放麦子 */

#include 

int main()
{
    unsigned long long x = ~(0LL);
    printf("%llu\n", x);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

AC的C语言程序（无符号长长整形）如下：

/* LQ0262 棋盘放麦子 */

#include 

int main()
{
    unsigned long long sum = 0, a = 1;
    for (int i = 1; i <= 64; i++)
        sum += a, a *= 2;
    printf("%llu\n", sum);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

AC的C语言程序（兆进制）如下：

/* LQ0262 棋盘放麦子 */

#include 

typedef long long LL;
#define MOD 1000000000000LL

int main()
{
    LL a0 = 1, a1 = 0, sum0 = 0, sum1 = 0, carry;

    for (int i = 1; i <= 64; i++) {
        /* sum += a; */
        sum0 += a0, carry = sum0 / MOD, sum0 %= MOD;
        sum1 += a1 + carry;

        /* a *= 2 */
        a0 *= 2, carry = a0 / MOD, a0 %= MOD;
        a1 *= 2, a1 += carry;
    }

    printf("%lld%012lld\n", sum1, sum0);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

AC的C语言程序（万进制）如下：

/* LQ0262 棋盘放麦子 */

#include 
#include 

typedef long long LL;
#define MOD 100000000LL
#define N 3
LL a[N], sum[N];

int main()
{
    memset(a, 0, sizeof a);
    memset(sum, 0, sizeof sum);

    a[0] = 1;
    for (int i = 1; i <= 64; i++) {
        /* sum += a; */
        LL carry = 0;
        for (int j = 0; j < N; j++) {
            sum[j] += a[j] + carry;
            carry = sum[j] / MOD;
            sum[j] %= MOD;
        }

        /* a *= 2 */
        carry = 0;
        for (int j = 0; j < N; j++) {
            a[j] = a[j] * 2 + carry;
            carry = a[j] / MOD;
            a[j] %= MOD;
        }
    }

    printf("%lld", sum[N - 1]);
    for (int i = N - 2; i >= 0; i--)
        printf("%08lld", sum[i]);
    printf("\n");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

AC的Java语言程序如下：

/* LQ0262 棋盘放麦子 */

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger sum = new BigInteger("0");
        BigInteger TWO  = new BigInteger("2");
        for (int i = 0; i < 64 ; i++)
            sum = sum.add(TWO.pow(i));
        System.out.println(sum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

AC的Java语言程序如下：

/* LQ0262 棋盘放麦子 */

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger sum = new BigInteger("0");
        BigInteger a = new BigInteger("1");
        BigInteger TWO  = new BigInteger("2");
        for (int i = 1; i <= 64 ; i++) {
            sum = sum.add(a);
            a = a.multiply(TWO);
        }
        System.out.println(sum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

AC的Python语言程序如下：

print(2**64-1)
1