fork download
copy 
  1. /*
  2.  * Language: Standard C++23 [-std=c++23]
  3.  * Author: Zang Vũ aka zvwgvx
  4.  * Github & Discord & Facebook: @zvwgvx
  5.  */
  6.  
  7. #pragma GCC optimize("fast-math,O3")
  8. #pragma GCC optimize("no-stack-protector") 
  9. #pragma GCC optimize("unroll-loops")
  10. // #pragma GCC optimize("Ofast")
  11. // #pragma GCC target("tune=native")
  12. // #pragma GCC target("avx,avx2,fma")
  13.  
  14. #include <bits/stdc++.h>
  15.  
  16. using namespace std;
  17.  
  18. #define ENV defined(LOCAL)
  19. #define el cout << '\n'
  20. #define rt return
  21. #define ll long long
  22. #define ull unsigned ll
  23. #define pii pair <int, int>
  24. #define pll pair <ll, ll>
  25. #define vi vector <int>
  26. #define vl vector <ll>
  27. #define vc vector <char>
  28. #define vvi vector <vector <int>>
  29. #define vvl vector <vector <ll>>
  30. #define mts multiset
  31. #define mtm multimap
  32. #define ump unordered_map
  33. #define ust unordered_set
  34. #define umts unordered_multiset
  35. #define umtm unordered_multimap
  36. #define priq priority_queue
  37.  
  38. template <typename T>
  39. T fgcd(T a, T b) {
  40.     if (!a || !b) rt a | b;
  41.     unsigned shift = __builtin_ctzll(a | b);
  42.     a >>= __builtin_ctzll(a);
  43.     while (b) {
  44.         b >>= __builtin_ctzll(b);
  45.         if (a > b) swap(a, b);
  46.         b -= a;
  47.     }
  48.     rt a << shift;
  49. }
  50.  
  51. template <typename T>
  52. T fpow(T base, T exp, T mod) {
  53.     T res = 1;
  54.     for (; exp; exp >>= 1, base = base * base % mod)
  55.         if (exp & 1) res = res * base % mod;
  56.     rt res;
  57. }
  58.  
  59. template <typename T> T lcm(T a, T b) { rt a * (b / fgcd(a, b)); }
  60. template <typename T> void maximize(T& a, T b) { if (a < b) a = b; }
  61. template <typename T> void minimize(T& a, T b) { if (a > b) a = b; }
  62. template <typename T> double lg(T a, T b) { rt log(b) / log(a); }
  63. template <typename T> ull P(T n, T k) { ull res = 1; for (int i = 0; i < k; i++) res *= (n - i); rt res; }
  64. template <typename T> ull C(T n, T k) { ull res = 1; for (int i = 1; i <= k; i++) res = res * (n - i + 1) / i; rt res; }
  65.  
  66. const int MOD = 1e9 + 7;
  67. const int INF = 1e9;
  68. const int LIMIT = 1e6 + 5;
  69.  
  70. #if ENV
  71. void open(const string& file) {
  72.     freopen((file + ".inp").c_str(), "r", stdin);
  73.     freopen((file + ".out").c_str(), "w", stdout);
  74. }
  75. auto start = clock();
  76. void time() { cout << "\n\n[rt] " << 1.0 * (clock() - start) / CLOCKS_PER_SEC; }
  77. #endif
  78.  
  79. ll get_exp(ll N, int p) {
  80.     ll e = 0;
  81.     ll pow = p;
  82.     while(pow <= N){
  83.         e++;
  84.         if(pow > N / p) break; 
  85.         pow *= p;
  86.     }
  87.     rt e;
  88. }
  89.  
  90. vi sieve(int lIMIT) {
  91.     vector<bool> is_prime(lIMIT + 1, true);
  92.     is_prime[0] = is_prime[1] = false;
  93.     for (int i = 2; i * i <= lIMIT; ++i){
  94.         if(is_prime[i]){
  95.             for (int j = i * i; j <= lIMIT; j += i)
  96.                 is_prime[j] = false;
  97.         }
  98.     }
  99.     vi primes;
  100.     for (int i = 2; i <= lIMIT; i++){
  101.         if(is_prime[i]) primes.push_back(i);
  102.     }
  103.     rt primes;
  104. }
  105.  
  106. signed main() { 
  107.     cin.tie(nullptr), cout.tie(nullptr)
  108.     -> ios_base::sync_with_stdio(false);
  109.  
  110.     #if ENV 
  111.         open("main");
  112.         srand(time(nullptr));
  113.     #endif
  114.  
  115.     vl tcase;
  116.     ll N;
  117.  
  118.     while (cin >> N) {
  119.         tcase.push_back(N);
  120.     }
  121.  
  122.     if (tcase.empty())
  123.         rt 0;
  124.  
  125.     ll max_n = 0;
  126.     for (auto x : tcase) {
  127.         if(x > max_n) max_n = x;
  128.     }
  129.  
  130.     int lim = (max_n < 2 ? 2 : (int)max_n);
  131.     vi primes = sieve(lim);
  132.  
  133.     for (auto n : tcase){
  134.         if(n == 1){
  135.             cout << 1; el;
  136.             continue;
  137.         }
  138.  
  139.         ll exp2 = get_exp(n, 2);
  140.         ll exp5 = get_exp(n, 5);
  141.  
  142.         ll result = fpow(2LL, (ll)(exp2 - exp5), 10LL);
  143.  
  144.         for (int p : primes) {
  145.             if(p > n) break;
  146.             if(p == 2 || p == 5) continue;
  147.             ll e = get_exp(n, p);
  148.             ll r = e % 4;
  149.             if(e > 0 && r == 0) r = 4;
  150.             result = (result * fpow((ll)p, (ll)r, 10LL)) % 10;
  151.         }
  152.  
  153.         cout << result % 10; el;
  154.     }
  155.  
  156.     #if ENV 
  157.         time();
  158.     #endif
  159.  
  160.     rt 0;   
  161. }
  162.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/21SERd
language:
C++14 (clang 8.0)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!