0

问题链接 - http://www.spoj.com/problems/LASTDIG/

摘要 - 给定 2 个非负整数 a 和 b，打印 a^b 的最后一位。

我尝试使用一种算法来使用更少的内存空间（ http://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method ）找到模幂，但我的解决方案出现 TLE（超出时间限制）错误。我应该进行哪些更改才能在 1 秒内运行我的代码？请注意，需要在 1 秒内运行 10 个测试用例。

我的解决方案：

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>

typedef long long LL;

using namespace std;


int ME(LL A, LL B)
{
    LL c=1;
    int E=0;

    while(E<B)
    {
        c=(c*A)%10;
        E++;
    }

    return c;
}

int main()
{
    int t;
    LL a, b;
    vector <int> lDigit(31);

    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>a>>b;

        if(b>=99999)
            lDigit[i]=ME(a, b);
        else
        {
            int temp=pow(a, b);
            lDigit[i]=temp%10;
        }
    }

    for(int i=0;i<t;i++)
        cout<<lDigit[i]<<endl;

    return 0;
}
4

1 回答 1

1

您使用的算法对于大幂运算会很慢。快速模幂运算考虑指数中的位，并且只需要 O(lg(n)) 次乘法/除法，而您的代码需要 O(n) 次乘法。以 10 亿为指数，差异约为 10 亿到 30 倍。请参阅从右到左的二进制方法。

来自维基百科的伪代码是

function modular_pow(base, exponent, modulus)
    Assert :: (modulus - 1) * (base mod modulus) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

在 C 中变成

int modular_pow(int base, int exponent, int modulus) {
    int result = 1;
    base = base % modulus;
    while (exponent) {
        if (exponent & 1) {
            result = (result * base) % modulus;
        }
        exponent >>= 1;
        base = base * base % modulus;
    }
    return result;
}

虽然您的代码针对 20 亿次指数运行 while 循环 20 亿次，但上面的代码运行循环约 32 次。

于 2014-08-18T09:25:16.727 回答