题目链接: https://vjudge.net/contest/540139#problem/B

题意

给出 n ，求 S = (1^n + 2^n + 3^n + 4^n) mod 5 的值。

(0 ≤ n ≤ 1e(1e5))

思路

打表。然后发现 4 的倍数全是 4，其他全是 0。

判断一下是否为 4 的倍数即可。然后这里有一个小技巧，因为 100 = 4*25，所以 100n 通通都是 4 的倍数。如果遇到一个大于 100 的数 x，只需要把它拆成 100n+(x-100n)，这里 (x-100n) = x%100，然后只需要判断这一部分能否被 4 整除即可。

考虑证明，由同余运算有

S
= (1^n + 2^n + 3^n + 4^n) mod 5
= (1^n + 2^n + (-2)^n + (-1)^n) mod 5

显然当 n 为奇数的时候 S = 0。当 n 为偶数的时候，我们发现 4 的倍数和非 4 的倍数不同，分类讨论一下。

1. n = 4k

S

= 2(2^(4k)+1^(4k)) mod 5

= 2(16^k+1) mod 5

= 2(1^k+1) mod 5

= 4

2. n = 4k+2

S

= 2(2^(4k+2)+1^(4k+2)) mod 5

= 2(4·16^k+1) mod 5

= 2(4·1^k+1) mod 5

= 2·5 mod 5

= 0

复杂度: O(1)

代码

#include <iostream>
#include <string>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;
int arr[maxN];

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  std::string str; std::cin >> str;
  if (str.size() > 1) { std::cout << ((str[str.size()-2] * 10 + str[str.size()-1]) % 4 ? 0 : 4); }
  else { std::cout << (str[str.size()-1] % 4 ? 0 : 4); }

  return 0;
}