快速幂

hdu 1061      http://hdu.hustoj.com/showproblem.php?pid=1061

 

 

 

Problem Description

Given a positive integer N, you should output the most right digit of N^N.

 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

 

Output

For each test case, you should output the rightmost digit of N^N.

 

Sample Input

2 3 4

 

Sample Output

7 6

Hint

In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

 

 

题意  ：   给定  s  是测试次数     ，再给定n       求　　　　n的n次方%10  的值   

 

 

 

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x));
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f;
const double eps=1e-12;
const int mod=10;
int ans,temp;
void qmi(ll a,ll b)
{
    if (b==1){
        ans=temp*a%mod;
        return ;
    }
    else if (b%2==1){
        temp=temp*a%mod;
        qmi(a*a%mod,b/2);
    }
    else if(b%2==0){
        qmi(a*a%mod,b/2);
    return ;
    }
} 
int main()
{
    int t;
    cin>>t;
    while (t--){
        ll n;
        cin>>n;
        temp=1;
        qmi(n,n);
        cout<<ans<<endl;
    }
    return 0;
}

 

 *******************************题目2**********************************************

 

链接：https://ac.nowcoder.com/acm/contest/392/B
来源：牛客网

题目描述

找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。
月月的其中一项作业是：给定正整数A、B、P，求${\mathrm{ABmodPABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。\; 因为月月的作业很多，所以有T组询问。}}^{}$

输入描述:

第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

输出描述:

输出T行，每行一个非负整数表示答案。

示例1

输入

2
2  5  10
57284938291657  827493857294857  384729583748273

输出

2
18924650048745

备注:

$\mathrm{1\le T\le 1031\le T\le 103，1\le A,B,P\le 1018}$

 

 

AC代码：

#include<iostream>
using namespace std;
typedef __int128 ll;    //此处若为64位会爆，变成128位

ll quick(ll a,ll b,ll p)
{
    ll ans=1;
    while (b){
        if (b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    long long a,b,p;
    int t;
    scanf("%d",&t);
    while (t--){
        scanf("%lld%lld%lld",&a,&b,&p);
        long long ans=quick(a,b,p);
        printf("%lld
",ans);
    }
}