c++ - 计算 floor(pow(2,n)/10) mod 10 - pow(2,n) 的数字总和

Question

这也是一个与数学相关的问题，但我想用 C++ 实现它...所以，我有一个 2^n 形式的数字，我必须计算它的数字总和(以 10 为基数；P)。我的想法是用下面的公式来计算:

sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...

对于它的所有数字:floor(n/floor(log2(10)))。

第一项很容易用模幂计算，但我在计算其他项时遇到了麻烦。由于 n 很大，而且我不想使用我的大整数库，所以我无法在没有模的情况下计算 pow(2,n)。第一项的代码片段:

while (n--){
    temp = (temp << 1) % 10;
};

但是第二个我不知道。我也不能单独floor它们，因为它会给出'0'(2/10)。有可能实现这一目标吗？(http://www.mathblog.dk/project-euler-16/ 是更简单的解决方案。)当然，如果无法使用此方法，我会寻找其他方法。 (例如，将数字存储在字节数组中，如链接中的注释所示)。

编辑:感谢现有的答案，但我正在寻找一些数学方法来解决它。我刚刚想到了一个想法，可以在没有 bignum 或 digit-vectors 的情况下实现，我要测试它是否有效。

所以，我有上面的等式求和。但是 2^n/10^k 可以写成 2^n/2^(log2 10^k) 即 2^(n-k*log2 10 )。然后我取它的小数部分和它的整数部分，并对整数部分进行模幂运算: 2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract( n-k*log2 10))。在最后一次迭代之后，我还将它与分数模 10 相乘。如果它不起作用或者如果我在上述想法中的某个地方错了，我坚持使用 vector 解决方案并接受答案。

编辑: 好吧，似乎用非整数模做模幂运算是不可能的(？)(或者我还没有找到任何相关信息)。所以，我正在做基于数字/vector 的解决方案。

代码不能完全工作!

它没有给出好的值:(1390 而不是 1366):

typedef long double ldb;

ldb mod(ldb x, ldb y){             //accepts doubles
    ldb c(0);
    ldb tempx(x);
    while (tempx > y){
        tempx -= y;
        c++;
    };
    return (x - c*y);
};

int sumofdigs(unsigned short exp2){
    int s = 0;
    int nd = floor((exp2) * (log10(2.0))) + 1;
    int c = 0;
    while (true){
        ldb temp = 1.0;
        int expInt = floor(exp2 - c * log2((ldb)10.0));
        ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
        while (expInt>0){
           temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
                //floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
            expInt--;
        };
        ldb r = pow(2.0, expFrac);
        temp = (temp * r);
        temp = mod(temp,10.0);
        s += floor(temp);
        c++;
        if (c == nd) break;
    };
    return s;
};

Answer 1

您可以使用其他问题 (C++ get each digit in int) 中提到的一些技术创建数字 vector ，然后迭代该 vector 并将所有内容相加。