3

有朋友问我：

如果2^10 = 1024 ，我们可以取 1024 并分解和总结它的数字：

1+0+2+4 = 7.

这很简单。

然而，当输入是2^30000（输入实际上是一个长字符串"1000..."）时——没有 .net 类型可以保存这个值。

所以必须有一个技巧来求和它的数字（十进制值的数字）......

编辑：

相关技巧（用于寻找10^20 - 16）

100 = 10^2（一个和两个零）

10^20 =（一个和 20 个零）

因此：

10^20 - 16 = 18 个 9，一个 8 和 4。

18*9+8+4 = 174

但是我还没有成功地将这个解决方案转换为我的问题。（我尝试了很多）。

*我将此问题标记为 .net，因为我可以使用 .net 库中的字符串函数、数学函数。*

问题

这里有什么技巧可以让我将许多数字相加x^n吗？

这里有什么诀窍？

编辑#2：添加了 .net2 标签（biginteger 不可用） - 我想知道没有 biginteger 我怎么能做到。（我正在寻找隐藏的技巧）

4

4 回答 4

7

您可以利用BigInteger结构来执行此操作。正如它在 MSDN 中所写

BigInteger 类型是一种不可变类型，它表示一个任意大的整数，其值在理论上没有上限或下限。

基本上在创建 BigInteger 实例并评估指数之后，您可以将其转换为字符串。之后，您将遍历该字符串的每个字符并将每个 char 转换为 int 数字。将所有这些 int 数字相加，您将得到答案。

BigInteger bi = new BigInteger(2);
var bi2 = BigInteger.Pow(bi, 30000);
BigInteger sum = new BigInteger();
foreach(var ch in bi2.ToString())
    sum = BigInteger.Add(sum, new BigInteger(int.Parse(ch.ToString())));
MessageBox.Show(bi2.ToString() + " - " + sum.ToString());
于 2013-04-27T08:04:14.913 回答
5

我不知道找到一个数字的基数为 10 位和的一般技巧。

但是，有一个简单的技巧可以找到一个数字的以10 位为底的根。

正如您所说，数字总和只是所有数字的总和。1024 的 10 位基数和是 1 + 2 + 4 = 7。65536 的 10 位基数和是 6 + 5 + 5 + 3 + 6 = 25。

数字根是当您重复数字总和直到只有一位数字时得到的。65536 的数字和是 25，所以数字根是 2 + 5 = 7。

诀窍是：如果你有 Z = X * Y，那么 DigitRoot(Z) = DigitRoot(DigitRoot(X) * DigitRoot(Y))。（练习给读者：证明它！提示：首先证明加法的相同恒等式。）

如果你有一个容易因式分解的数——最容易因式分解的数是 2 n——那么很容易递归地计算出数字根： 2 16 = 2 8 * 2 8，所以 DigitRoot(2 16 ) = DigitRoot( DigitRoot(2 8 ) * DigitRoot(2 8 )) -- 我们只是让问题变得更小了。现在我们不必计算 2 16，我们只需要计算 2 8。您当然可以将这个技巧与 2 30000一起使用——将其分解为 DigitRoot(DigitRoot(2 15000 * DigitRoot(2 15000 ))。如果 2 15000太大了，进一步分解；继续分解它，直到你有一个小到可以解决的问题。

说得通？

于 2013-04-27T14:47:19.270 回答
2

我不相信这里有什么技巧。您展示的后一个技巧有效，因为数字和结果都是十进制数。

For example:
1267 = 1*10^3 + 2*10^2 + 6*10^1 + 7*10^0

因此，您在功率和总和之间存在明显的相关性。但不幸的是，如果您想将二进制数或 2 的幂转换为十进制数，这是行不通的。最大的努力是减少增加基数的能力。

2^3000 = 4^1500 = 16^750 = 256^375

但是正如您所看到的，该系列跳过了以 10 为基数。遗憾的是，这意味着您需要将最终结果计算为十进制数，然后才能将其转换为 10 的幂。使这个技巧不起作用。

于 2013-04-27T08:31:27.723 回答
1

来自http://blog.singhanuvrat.com/problems/sum-of-digits-in-ab：

public class Problem_16 {
    public long sumOfDigits(int base, int exp) {
        int numberOfDigits = (int) Math.ceil(exp * Math.log10(base));
        int[] digits = new int[numberOfDigits];
        digits[0] = base;
        int currentExp = 1;

        while (currentExp < exp) {
            currentExp++;
            int carry = 0;
            for (int i = 0; i < digits.length; i++) {
                int num = base * digits[i] + carry;
                digits[i] = num % 10;
                carry = num / 10;
            }
        }

        long sum = 0;
        for (int digit : digits)
            sum += digit;

        return sum;
    }

    public static void main(String[] args) {
        int base = 2;
        int exp = 3000;
        System.out.println(new Problem_16().sumOfDigits(base, exp));
    }
}

C＃

public class Problem_16 {
    public long sumOfDigits(int base1, int exp) {
        int numberOfDigits = (int) Math.Ceiling(exp * Math.Log10(base1));
        int[] digits = new int[numberOfDigits];
        digits[0] = base1;
        int currentExp = 1;

        while (currentExp < exp) {
            currentExp++;
            int carry = 0;
            for (int i = 0; i < digits.Length; i++) {
                int num = base1 * digits[i] + carry;
                digits[i] = num % 10;
                carry = num / 10;
            }
        }

        long sum = 0;
        foreach (int digit in  digits)
            sum += digit;

        return sum;
    }
}


void Main()
{
     int base1 = 2;
        int exp = 3000000;
        Console.WriteLine (new Problem_16().sumOfDigits(base1, exp));

}
于 2013-05-07T04:21:20.500 回答