级数之和：a^0+2a^1 + 3*a^2 + 4*a^3 + … + n*a^(n-1) (mod M)
Sum of series: a^0+2a^1 + 3*a^2 + 4*a^3 + … + n*a^(n-1) (mod M)
谁能给我一个大 n 的有效算法的想法，它使用递归函数而不是几何求和公式执行 O(log(n))。
您需要使用等比级数和的公式：a^1 + a^2 + ... a^n = (a^(n+1) - 1) / (a - 1)。使用 exponentiation by squaring you can compute (a^(n+1) - 1) in O(log(n)). If M is prime dividing by (a - 1) is simply one more exponentiation - for any U coprime with a prime number p, U^(-1) (mod p) = U^(p-2) (mod p). You can prove this using Fermat's little theorem.
首先，正如你所说的 M < 105，你知道所有数字最多需要 16 位，所以只要稍微谨慎一点，你就不会被精确的问题所困扰。
接下来，如an(mod M) = (a(mod M)) n(mod M)，也可以说a5
接下来如果你记下un=a0+a1... an-1 (mod M)，可以使用如下递归：
- u2k = uk+akuk (mod 男)
- uk+1 = uk+ak (mod M)
- u2k+1 = uk+1+ak+1u k (mod M) = uk+ak+a*akuk (mod M)
给定一个数字 n，你会找到大约 log2(n) 个数字 n，n/2，n/4，...，1 和使用上述公式，您可以轻松计算 un/2i 和 an/2i 知道 un/2i+1 和 an/2i+1
由于不同的测试，这个算法可能写起来并不简单（特别不要忘记 mod M 操作确保没有溢出），但它 是 O(log2(n))
谁能给我一个大 n 的有效算法的想法，它使用递归函数而不是几何求和公式执行 O(log(n))。
您需要使用等比级数和的公式：a^1 + a^2 + ... a^n = (a^(n+1) - 1) / (a - 1)。使用 exponentiation by squaring you can compute (a^(n+1) - 1) in O(log(n)). If M is prime dividing by (a - 1) is simply one more exponentiation - for any U coprime with a prime number p, U^(-1) (mod p) = U^(p-2) (mod p). You can prove this using Fermat's little theorem.
首先，正如你所说的 M < 105，你知道所有数字最多需要 16 位，所以只要稍微谨慎一点，你就不会被精确的问题所困扰。
接下来，如an(mod M) = (a(mod M)) n(mod M)，也可以说a
接下来如果你记下un=a0+a1... an-1 (mod M)，可以使用如下递归：
- u2k = uk+akuk (mod 男)
- uk+1 = uk+ak (mod M)
- u2k+1 = uk+1+ak+1u k (mod M) = uk+ak+a*akuk (mod M)
给定一个数字 n，你会找到大约 log2(n) 个数字 n，n/2，n/4，...，1 和使用上述公式，您可以轻松计算 un/2i 和 an/2i 知道 un/2i+1 和 an/2i+1
由于不同的测试，这个算法可能写起来并不简单（特别不要忘记 mod M 操作确保没有溢出），但它 是 O(log2(n))