ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

yukicoder No.167 : N^M mod 10

概要

N^M mod 10を求めよ。

N,Mは非常に大きな値

http://yukicoder.me/problems/373

解法

10の余りを求めるので、Nの1の位のみを考える。

0~9のそれぞれの冪乗 mod 10を列挙していくと規則性があることが分かる。
それらの規則性の周期は1,2,4となっているので、M mod 4について考える。
M mod 4はM mod 100の値を見れば分かる。

この方法ならN,Mが非常に大きな値でも解を求めることができる。

またM=0のときの処理には注意。

ちなみにJava等の多倍長整数でゴリ押すことも可能。
(BigInteger強い)

ソースコード

C++による解法

#include <bits/stdc++.h>

#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define F first
#define S second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

int main() {
  // ios_base::sync_with_stdio(false);
  string N, M;
  cin >> N >> M;

  if(M == "0") cout << "1" << endl;
  else {
    int n = N.back() - '0';
    M = "0" + M;
    int sz = M.size();
    int m = 10 * (M[sz - 2] - '0') + (M[sz - 1] - '0');
    
    cout << (int)pow(n, (m + 3) % 4 + 1) % 10 << endl;
  }
  
  return 0;
}

Javaによる解法

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main {
    
    void run() {
        Scanner sc = new Scanner(System.in);
        BigInteger N = sc.nextBigInteger();
        BigInteger M = sc.nextBigInteger();
        System.out.println(N.modPow(M, BigInteger.TEN));
    }


    public static void main(String[] args) {
        new Main().run();
    }

}