time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There exists an island called Arpa’s land, some beautiful girls live there, as ugly ones do.

Mehrdad wants to become minister of Arpa’s land. Arpa has prepared an exam. Exam has only one question, given n, print the last digit of 1378n.

Mehrdad has become quite confused and wants you to help him. Please help, although it’s a naive cheat.

Input
The single line of input contains one integer n (0??≤??n??≤??109).

Output
Print single integer — the last digit of 1378n.

Examples
input
1
output
8
input
2
output
4
Note
In the first example, last digit of 13781?=?1378 is 8.

In the second example, last digit of 13782?=?1378·1378?=?1898884 is 4.

【題目鏈接】:http://codeforces.com/problemset/problem/742/A

【題解】

快速冪取模;
把那個數(shù)用快速冪乘一下；乘的時候取個位數(shù)就好;

【完整代碼】

#include <cstdio> #include <cstdlib> #include <cmath> #include <set> #include <map> #include <iostream> #include <algorithm> #include <cstring> #include <queue> #include <vector> #include <stack> #include <string> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se secondtypedef pair<int,int> pii; typedef pair<LL,LL> pll;void rel(LL &r) {r = 0;char t = getchar();while (!isdigit(t) && t!='-') t = getchar();LL sign = 1;if (t == '-')sign = -1;while (!isdigit(t)) t = getchar();while (isdigit(t)) r = r * 10 + t - '0', t = getchar();r = r*sign; }void rei(int &r) {r = 0;char t = getchar();while (!isdigit(t)&&t!='-') t = getchar();int sign = 1;if (t == '-')sign = -1;while (!isdigit(t)) t = getchar();while (isdigit(t)) r = r * 10 + t - '0', t = getchar();r = r*sign; }//const int MAXN = x; const int dx[9] = {0,1,-1,0,0,-1,-1,1,1}; const int dy[9] = {0,0,0,-1,1,-1,1,-1,1}; const double pi = acos(-1.0);LL n; LL ans = 1;void f(LL x) {if (x==0)return;f(x>>1);ans = (ans * ans)%10;if (x&1)ans=(ans*1378)%10; }int main() {//freopen("F:\\rush.txt","r",stdin);cin>>n;if (n==0)puts("1");else{f(n);cout << ans << endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AWCXV/p/7626859.html

總結(jié)

以上是生活随笔為你收集整理的【codeforces 742A】Arpa’s hard exam and Mehrdad’s naive cheat的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。