c - 如何降低以下循环的时间复杂度？

Question

for(i=0;i<N-2;i++)
       count=(count*10)%M;

这里，N 可以达到 10^18，M 是 (10^9 +7)。因为这个循环需要 O(n) 的时间来执行，所以我在我的代码中得到了 TLE。有什么办法可以降低时间复杂度？

Answer 1

问题基本上是:

(count*a^b)%mod = ((count%mod)*((a^b)%mod))%mod

a = 10, b = 10^18

你可以找到 ((a^b)%mod) 使用:

long long power(long long x, long long y, long long p)
{
    long long res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or 
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;  
    }
    return res;
}

幂函数的时间复杂度为 O(log y)。

在您的例子中，count 是一个 1 位数字，因此我们可以简单地将其与 (count%mod) 相乘，最后对结果取模。如果 count 也是一个很大的数字，并且会导致溢出，那么我们可以这样做:

long long mulmod(long long a, long long b, long long mod)
{
    long long res = 0; // Initialize result
    a = a % mod;
    while (b > 0)
    {
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;

        // Multiply 'a' with 2
        a = (a * 2) % mod;

        // Divide b by 2
        b /= 2;
    }

    // Return result
    return res % mod;
}