結果

問題 No.167 N^M mod 10
コンテスト
ユーザー okaduki
提出日時 2018-01-06 04:29:42
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 807 ms / 1,000 ms
コード長 9,470 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,425 ms
コンパイル使用メモリ 188,208 KB
実行使用メモリ 174,208 KB
最終ジャッジ日時 2024-09-22 01:45:04
合計ジャッジ時間 10,000 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

struct BigInt {
public:
  using LL = long long int;
  static const LL BASE = 1000000000;
  const int DIG = 9;

  bool neg;
  std::vector<LL> dig;

  BigInt() : neg(false), dig(1, 0ll) {}
  BigInt(const char* str) : BigInt(std::string(str)) {}
  BigInt(const std::string& str) : neg(false) {
	if(str.empty()){
	  dig.assign(1, 0);
	  return;
	}

	int b = 0;
	if(str[b] == '-'){
	  neg = true;
	  ++b;
	}

	LL crt = 0;
	LL p = 1;
	for(int i=(int)(str.size())-1;i>=b;--i,p*=10){
	  if(p == BASE){
		dig.emplace_back(crt);
		crt = 0;
		p = 1;
	  }
	  if(!isdigit(str[i])){
		throw "Non digit is given.";
	  }
	  crt += p * (str[i] - '0');
	}
	dig.emplace_back(crt);
	norm();
  }
  BigInt(LL x) : neg(x<0), dig(1, std::abs(x)){
	for(unsigned int i=0;i<dig.size();++i){
	  if(dig[i] >= BASE){
		dig.emplace_back(dig[i] / BASE);
		dig[i] %= BASE;
	  }
	}
  }
  BigInt& operator=(const BigInt& rhs){
	neg = rhs.neg;
	dig = rhs.dig;
	return *this;
  }
  BigInt& operator=(LL x){ return *this = BigInt(x); }
  BigInt& operator=(const char* s){ return *this = BigInt(s); }
  BigInt& operator=(const std::string& s){ return *this = BigInt(s); }

  bool iszero() const {
	return dig.size() == 1 && dig[0] == 0;
  }

  BigInt operator-() const {
	BigInt res = *this;
	if(!res.iszero())
	  res.neg = !res.neg;
	return res;
  }

  //! ignoring sign
  static int comp(const BigInt& l, const BigInt& r){
	if(l.dig.size() != r.dig.size())
	  return (l.dig.size() < r.dig.size() ? -1: 1);
   
	for(int i=(int)(l.dig.size())-1;i>=0;--i){
	  if(l.dig[i] != r.dig[i])
		return (l.dig[i] < r.dig[i] ? -1: 1);
	}
	return 0;
  }
  //! add ignoring sign
  static void add(BigInt& l, const BigInt& rhs){
	unsigned int i;
	for(i=0;i<rhs.dig.size();++i){
	  if(l.dig.size() <= i){
		l.dig.emplace_back(rhs.dig[i]);
	  }
	  else{
		l.dig[i] += rhs.dig[i];
		if(l.dig[i] >= BASE){
		  l.dig[i] -= BASE;
		  if(l.dig.size() <= i+1)
			l.dig.emplace_back(0);
		  l.dig[i+1]++;
		}
		else if(l.dig[i] < 0){
		  l.dig[i] += BASE;
		  if(l.dig.size() <= i+1)
			l.dig.emplace_back(0);
		  l.dig[i+1]--;
		}
	  }
	}
	for(;i<l.dig.size();++i)
	  if(l.dig[i] >= BASE){
		l.dig[i] -= BASE;
		if(l.dig.size() <= i+1)
		  l.dig.emplace_back(0);
		l.dig[i+1]++;
	  }
  }
  // subtract ignoring sign, supposed to l >= rhs
  static void sub(BigInt& l, const BigInt& rhs){
	unsigned int i;
	for(i=0;i<rhs.dig.size();++i){
	  l.dig[i] -= rhs.dig[i];
	  if(l.dig[i] < 0){
		l.dig[i] += BASE;
		l.dig[i+1]--;
	  }
	}
	for(;i<l.dig.size();++i)
	  if(l.dig[i] < 0){
		l.dig[i] += BASE;
		l.dig[i+1]--;
	  }
  }
  
  void flip(){
	for(unsigned int i=0;i<dig.size();++i)
	  dig[i] *= -1;
  }
  void norm(){
	while(dig.size() > 1 && dig.back() == 0) dig.pop_back();
	if(iszero()) neg = false;
  }
  bool operator==(const BigInt& rhs) const {
	if(neg != rhs.neg || dig.size() != rhs.dig.size()) return false;
	return comp(*this, rhs) == 0;
  }
  bool operator<(const BigInt& rhs) const {
	if(neg != rhs.neg) return neg? true: false;
	if(neg) return comp(rhs, *this) == -1;
	return comp(*this, rhs) == -1;
  }
  bool operator<=(const BigInt& rhs) const {
	if(neg != rhs.neg) return neg? true: false;
	if(neg) return comp(rhs, *this) <= 0;
	return comp(*this, rhs) <= 0;
  }
  bool operator!=(const BigInt& rhs) const { return !(*this == rhs); }
  bool operator>(const BigInt& rhs)  const { return rhs < *this; }
  bool operator>=(const BigInt& rhs) const { return rhs <= *this; }

  // ignoring sign
  void incl(){
	for(unsigned int i=0;i<dig.size();++i)
	  if(++dig[i] == BASE){
		dig[i] = 0;
		if(i+1 == dig.size()){
		  dig.push_back(1);
		  break;
		}
	  }
	  else break;
  }
  // ignoring sign
  void decl(){
	if(iszero()){
	  dig[0] = 1;
	  neg = true;
	  return;
	}
	for(unsigned int i=0;i<dig.size();++i)
	  if(--dig[i] == -1)
		dig[i] = BASE-1;
	  else break;
	norm();
  }
  BigInt& operator++(){
	if(!neg) incl(); else decl();
	return *this;
  }
  BigInt operator++(int){
	BigInt res = *this;
	if(!neg) incl(); else decl();
	return res;
  }
  BigInt& operator--(){
	if(!neg) decl(); else incl();
	return *this;
  }
  BigInt operator--(int){
	BigInt res = *this;
	if(!neg) decl(); else incl();
	return res;
  }

  BigInt& operator+=(const BigInt& rhs){
	if(!this->neg){
	  if(!rhs.neg)
		add(*this, rhs);
	  else{
		if(comp(*this, rhs) >= 0)
		  sub(*this, rhs);
		else{
		  flip();
		  add(*this, rhs);
		  neg = true;
		}
	  }
	}
	else{
	  if(!rhs.neg){
		if(comp(rhs, *this) >= 0){
		  flip();
		  add(*this, rhs);
		  neg = false;
		}
		else
		  sub(*this, rhs);
	  }
	  else
		add(*this, rhs);
	}

	norm();
	return *this;
  }
  BigInt& operator-=(const BigInt& rhs){ return *this += -rhs; }
  BigInt operator+(const BigInt& rhs) const { BigInt res = *this; return res += rhs; }
  BigInt operator-(const BigInt& rhs) const { BigInt res = *this; return res -= rhs; }
  BigInt operator*(const BigInt& rhs) const {
	BigInt res;
	res.dig.assign(dig.size() + rhs.dig.size() + 1, 0ll);
	res.neg = neg ^ rhs.neg;

	for(unsigned i=0;i<rhs.dig.size();++i){
	  if(rhs.dig[i] == 0) continue;
	  for(unsigned j=0;j<dig.size();++j){
		res.dig[i+j] += rhs.dig[i] * dig[j];
		if(res.dig[i+j] >= BASE){
		  res.dig[i+j+1] += res.dig[i+j] / BASE;
		  res.dig[i+j] %= BASE;
		}
	  }
	}
	res.norm();

	return res;
  }
  BigInt operator*=(const BigInt& rhs){ return *this = *this * rhs; }

  static void divll(BigInt& x, LL& r, LL d){
	bool lneg = x.neg;
	x.neg ^= (d < 0);
	if(d < 0) d *= -1;
	
	r = 0;
	for(int i=(int)x.dig.size()-1;i>=0;--i){
	  r = r * BASE + x.dig[i];
	  x.dig[i] = r / d;
	  r %= d;
	}
	x.norm();

	if(r != 0 && lneg)
	  r *= -1;
  }

  void powB(LL x){
	if(iszero()) return;
	while(x > 0){
	  dig.insert(dig.begin(), 0ll);
	  --x;
	}
  }
  static void divmod(BigInt& q, BigInt& r, const BigInt& lhs, const BigInt& rhs){
	int cmp = comp(lhs, rhs);
	if(cmp < 0){
	  q.dig = std::vector<LL>(1, 0ll);
	  q.neg = false;
	  r = lhs;
	  return;
	}
	else if(cmp == 0){
	  q.dig = std::vector<LL>(1, 1ll);
	  q.neg = false;
	  r.dig = std::vector<LL>(1, 0ll);
	  r.neg = false;
	  return;
	}
	if(rhs.dig.size() == 1){
	  LL rl;
	  q = lhs;
	  divll(q, rl, rhs.dig[0] * (rhs.neg?-1ll:1ll));
	  r = rl;
	  return;
	}

	q.neg = r.neg = false;
	
	int u = lhs.dig.size() - rhs.dig.size() + 1;
	q.dig.assign(u+1, 0ll);

	LL K = BASE / (rhs.dig.back() + 1);
	BigInt ltmp = lhs, rtmp = rhs;
	ltmp.neg = rtmp.neg = false;

	if(K > 1){
	  ltmp *= K;
	  rtmp *= K;
	}

	LL x = ltmp.dig.back() / rtmp.dig.back();
	if(x == 0){
	  --u;
	  x = (ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size()-2]) / rtmp.dig.back();
	}
	BigInt w = 0ll;
	while(true){
	  w = rtmp;
	  w.powB(u);
	  if(comp(w, ltmp) > 0){
		--u;
		continue;
	  }
	  while(true){
		w = rtmp * x;
		w.powB(u);
		if(comp(w, ltmp) <= 0) break;
		--x;
	  }

	  q.dig[u--] = x;
	  ltmp -= w;
	  if(ltmp == 0ll || u < 0) break;

	  x = std::min(BASE-1,
				   (ltmp.dig.back() * BASE + ltmp.dig[ltmp.dig.size()-2]) / rtmp.dig.back());
	}
	q.norm();

	r = ltmp;
	if(ltmp != 0ll) divll(r, x, K);
	q.neg = lhs.neg ^ rhs.neg;
	r.neg = lhs.neg;
	r.norm();
  }

  BigInt operator/(const BigInt& rhs) const {
	BigInt q, r;
	divmod(q, r, *this, rhs);
	return q;
  }
  BigInt operator%(const BigInt& rhs) const {
	BigInt q, r;
	divmod(q, r, *this, rhs);
	return r;
  }
  BigInt& operator/=(BigInt rhs){ return *this = *this / rhs; }
  BigInt& operator%=(BigInt rhs){ return *this = *this % rhs; }

  std::string to_string() const {
	assert(!dig.empty());
	std::string res = neg? "-": "";

	std::ostringstream os;
	os << std::to_string(dig.back());
	for(int i=(int)(dig.size())-2;i>=0;--i){
	  os << std::setfill('0') << std::setw(DIG) << dig[i];
	}
	res += os.str();
	return res;
  }
  // convert long long int anyway
  LL to_ll() const {
	LL res = 0, p = 1;
	for(unsigned int i=0;i<dig.size();++i){
	  res += dig[i] * p;
	  p *= BASE;
	}
	return res * (neg? -1ll: 1);
  }
};
std::ostream& operator<<(std::ostream& os, const BigInt& x){ return os << x.to_string(); }

BigInt pow(BigInt a, BigInt b){
  if(b == 0ll) return 1ll;
  return pow(a*a%10, b/2) * (b%2==1? a: 1ll) % 10;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  string sa, sb;
  cin >> sa >> sb;
  BigInt a = sa, b = sb;

  cout << pow(a, b) % 10 << endl;

  return 0;
}
0