http://acm.hdu.edu.cn/showproblem.php?pid=1061
题意：
给定一个整数T，有T组数据，每组包含一个整数N,(N<=1e9)求每组数据N的N次方最后一个数字。
思路：
快速幂取模，基于以下公式：
(a*b)%m=( (a%m)*(b%m) )%m;
代码：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string> #include<iomanip> #include<algorithm> #include<string.h> #include<queue> using namespace std; const int maxn=5e5+10; const int inf=2147483647; typedef long long ll; ll n=1e9+10; ll mod(ll a,ll b) { if(b==1) return a; ll s=mod(a,b/2)%10; if(b%2==0) return (s*s)%10; else return (s*s*a)%10; } int main() { int t; cin>>t; while(t--) { cin>>n; cout<<mod(n,n)<<endl; } system("pause"); return 0; }
快速幂的非递归写法：
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<string> #include<iomanip> #include<algorithm> #include<string.h> #include<queue> using namespace std; const int maxn=5e5+10; const int inf=2147483647; typedef long long ll; ll n=1e9+10; ll mod(ll a,ll b) { ll sum=1; while(b) { if(b&1) sum=(sum*a)%10; b>>=1; a=(a*a)%10; } return sum; } int main() { int t; cin>>t; while(t--) { cin>>n; cout<<mod(n,n)<<endl; } system("pause"); return 0; }