题目描述
- 原文
Nestor was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives him two numbers a and b. The problem consist of finding the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000), a and b both are not 0. You have to find the last digit of \(a^{b}\) .
- 中文翻译
Nestor 在数学课上做了三天的作业,但他已经厌倦了大量的运算,明天就该完成任务了。数学老师给了他两个数字 a 和 b。问题是找出基数 a 和指数 b 的结果的最后一位数。请帮助 Nestor 解决这个问题。老师给了你两个整数:基数 a(0 <= a <= 20)和指数 b(0 <= b <= 2,147,483,000),a 和 b 都不为 0。您必须找出 \(a^{b}\) 的最后一位数。
Input
The first line of input contains an integer t, the number of test cases (t <= 30). t test cases follow. For each test case will appear a and b separated by space.
第一行输入包含一个整数 t,即测试用例数(t <= 30)。每个测试用例的 a 和 b 用空格隔开。
Output
For each test case output an integer per line representing the result.
每个测试用例每行输出一个整数,代表测试结果。
Example
Input | Output |
---|---|
2 3 10 6 2 |
9 6 |
题解
一道快速幂&取余运算的模板题(笑-)。
快速幂
快速幂是一种能迅速把\(a^{b}\) 求出来的算法,可以降低时间复杂度,防止TLE。
这里主要用了二分和递归的思路,把底数进行二分。当指数为偶数时,底数进行相乘,将指数除以2;当指数为奇数的时候,提出来一项底数,用ans进行积累,然后再按照偶数的方法递归。
long long qpow(long a,long n)
{
long long ans = 1;
while(n)
{
if (n % 2) ans *= a;//指数为奇数
a = a * a;//底数平方
n /= 2;//指数减半
}
return ans;
}
大数取模
- 原理展示
#include <iostream>
typedef long long ll;
using namespace std;
#define endl '\n'
int main()
{
ll base,power;
cin >> base >> power;
if (base == 0 && power == 0) break;
ll res = 1;
//执行power次循环,每次结果都乘一个base,即base的power次方
for (ll i = 1;i <= power;i++)
{
res = res * base;
res = res % 10;
}
ll ans = res % 10;
cout << ans << endl;
return 0;
}
AC代码
#include <iostream>
typedef long long ll;
#define endl '\n'
using namespace std;
int t; ll a,b;ll c;
ll qpow(ll a,ll n)
{
ll ans = 1;
while(n)
{
if (n & 1) ans = ans * a % 10;//位运算
a = a * a % 10;
n >>= 1;//n >> 1可将原数减半,n >>= 1等价于n = n / 2
}
return ans;
}
void solve()
{
cin>>a>>b;
c=qpow(a,b);
cout<<c<<endl;
}
int main()
{std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);//降低时间复杂度
cin>>t;
while(t--)
{
solve();
}
return 0;
}
标签:取模,digit,last,power,ll,long,base,ans,Nestor
From: https://www.cnblogs.com/ning0713/p/18518146