此文章可以使用目录功能哟↑(点击上方[+])
HDU 1097 A hard puzzle
Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b's the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.
Input
There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)
Output
For each test case, you should output the a^b's last digit number.
Sample Input
8 800
Sample Output
6
Problem Idea
解题思路:
【题意】
给你一个a和b,问a^b的最后一位数是多少
【类型】
快速幂
【分析】
乘法快速幂在幂运算方面还是比较常见的
通常,在幂运算中,幂较大时就会采用快速幂来缩短执行时间
而不是十分暴力的一项项乘
快速幂过程:
①对于奇数次幂
②对于偶数次幂
套个快速幂模板,此问题解决
【时间复杂度&&优化】
O(logn)
题目链接→HDU 1097 A hard puzzle
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 50005;
const int M = 5005;
const int inf = 1000000007;
const int mod = 1000000007;
__int64 Quick_Mod(int a, int b, int m)
{__int64 res = 1,term = a % m;while(b){if(b & 1) res = (res * term) % m;term = (term * term) % m;b >>= 1;}return res%m;
}
int main()
{int a,b;while(~scanf("%d%d",&a,&b))printf("%I64d\n",Quick_Mod(a,b,10));return 0;
}