最后的幂数

Question

我有个小问题。任务是接受变量 d 的输入——这意味着测试次数，以及输出变量 a 和 b。每个测试都是针对另一对 a 和 b。这段代码的结果应该是 a^b 求幂的最后一个数。示例：

//input
2 (it is d)
2 3 (a,b)
3 3 (a,b)

//output
8
7

这就是我尝试这样做的方式：

#include <iostream>
#include <cmath>

using namespace std;
int potega(int a, int b);

int main()
{   
int d;
int i;
cin >> d;
int t[d];
int a;
int b;
for(i=0; i<=d-1; i++)
{
    cin >> a >> b;
    t[i]=pow(a%10,b);
}
for(i=0; i<=d-1; i++)
{
    cout << t[i]%10 << endl;

 }
}

你有什么建议吗？我是初学者。执行时间应该小于0.529s。

Answer 1

您可以将数字分解为其平方幂，而不是遍历每个幂。

因此，如果您说 7 的指数与 (1 + 2 + 4) 完全相同，那么您可以使用指数的 1、2 和 4 次方，这将显着加快指数的速度。如果您有指数 9 (8 + 1)，则将数字平方 3 次以获得 8 次方，然后跳过乘法中的 2 次方和 4 次方。

因此，对于任何给定的两个数字，您将存储数字的当前 a^(2^n) 次方，然后检查此特定次方是否在 b 的二进制表示中。

这也称为平方求幂，您可以在 this wiki site 上阅读更多相关信息。除了在您的修改中，您实际上总是存储剩余的 %10 个数字而不是完整的数字。

Answer 2

如果有人需要解决方案：

/*for any a last number of a^b = last number of a^b+4 so: */
if (b%4==0)
{
    b=4;
}
else b=b%4;

它将执行速度从 1 秒提高到不到 0.01 秒:)

最后的幂数

Last number of exponentiation

c++

exponentiation