fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <unordered_map>
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const ll INF = LLONG_MAX;
  7. typedef long double ld;
  8. typedef string ss;
  9. typedef vector<long long> vll;
  10. typedef stack<ll> skll;
  11. typedef pair<char, ll> pci;
  12. typedef pair<ll, ll> pll;
  13. typedef map<ll, ll> mll;
  14. typedef map<char, ll> mcl;
  15.  
  16. #define pb push_back
  17. #define conti continue;
  18. #define fi first
  19. #define se second
  20. #define pr(a, b) pb(make_pair(a, b))
  21. #define mkp(a, b) make_pair(a, b)
  22. #define nl '\n'
  23. #define all(v) v.begin(), v.end()
  24. #define max(a, b) (a > b ? a : b)
  25. #define min(a, b) (a < b ? a : b)
  26. #define fost(i, a, b, d) for (ll i = a; i < b; i += d)
  27. #define ofst(i, a, b, d) for (ll i = a; i > b; i -= d)
  28. #define forb(i, a, b) for (int i = a; i < b; i++)
  29. #define fon(i, a, b) for (int i = a; i >= b; i--)
  30. #define fo(i, n) for (int i = 0; i < n; i++)
  31. #define itmp(mp) for (auto it = mp.begin(); it != mp.end(); it++)
  32. #define start_clock() auto start_time = std::chrono::high_resolution_clock::now();
  33. #define measure()                                            \
  34.   auto end_time = std::chrono::high_resolution_clock::now(); \
  35.   cerr << (end_time - start_time) / std::chrono::milliseconds(1) << "ms" << endl;
  36. #define yes cout << "YES" << nl;
  37. #define no cout << "NO" << nl;
  38.  
  39. /*-----------------------------debug----------------------------*/
  40. vector<string> vec_splitter(string s)
  41. {
  42.   s += ',';
  43.   vector<string> res;
  44.   while (!s.empty())
  45.   {
  46.     res.push_back(s.substr(0, s.find(',')));
  47.     s = s.substr(s.find(',') + 1);
  48.   }
  49.   return res;
  50. }
  51. void debug_out(
  52.     vector<string> __attribute__((unused)) args,
  53.     __attribute__((unused)) int idx,
  54.     __attribute__((unused)) int LINE_NUM) { cerr << endl; }
  55. template <typename Head, typename... Tail>
  56. void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T)
  57. {
  58.   if (idx > 0)
  59.     cerr << ", ";
  60.   else
  61.     cerr << "Line(" << LINE_NUM << ") ";
  62.   stringstream ss;
  63.   ss << H;
  64.   cerr << args[idx] << " = " << ss.str();
  65.   debug_out(args, idx + 1, LINE_NUM, T...);
  66. }
  67. #ifndef XOX
  68. #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
  69. #else
  70. #define debug(...) 42
  71. #endif
  72.  
  73. /*-----------------------------debug----------------------------*/
  74. /*-----------------------------printfs----------------------------*/
  75.  
  76. void parr(ll a[], ll n)
  77. {
  78.   for (ll i = 0; i < n; i++)
  79.   {
  80.     cout << a[i] << " ";
  81.   }
  82.   cout << endl;
  83. }
  84. void pvec(vector<ll> v)
  85. {
  86.   for (ll i = 0; i < v.size(); i++)
  87.   {
  88.     cout << v[i] << " ";
  89.   }
  90.   cout << endl;
  91. }
  92. struct custom_hash
  93. {
  94.   static uint64_t splitmix64(uint64_t x)
  95.   {
  96.     x += 0x9e3779b97f4a7c15;
  97.     x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  98.     x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  99.     return x ^ (x >> 31);
  100.   }
  101.  
  102.   size_t operator()(uint64_t x) const
  103.   {
  104.     static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  105.     return splitmix64(x + FIXED_RANDOM);
  106.   }
  107. };
  108. /*----------------------------printfs----------------------------*/
  109. /*----------------------------mint_stuff----------------------------*/
  110. ll extgcd(ll a, ll b, ll &x, ll &y)
  111. {
  112.   x = 1, y = 0;         // xa+yb=a at all times
  113.   ll q, x1 = 0, y1 = 1; // x1a+y1b=b at all times
  114.   while (a && b)
  115.   {
  116.     if (a > b)
  117.     {
  118.       q = a / b;
  119.       x -= q * x1;
  120.       y -= q * y1;
  121.       a -= q * b;
  122.     }
  123.     else
  124.     {
  125.       q = b / a;
  126.       x1 -= q * x;
  127.       y1 -= q * y;
  128.       b -= q * a;
  129.     }
  130.   }
  131.   if (a == 0)
  132.   {
  133.     x = x1;
  134.     y = y1;
  135.     return b;
  136.   }
  137.   return a;
  138. }
  139. const ll mod = 4;
  140. struct mint
  141. {
  142.   ll x;
  143.   mint() : x(0) {}
  144.   mint(ll y)
  145.   {
  146.     if (y >= 0 && y < mod)
  147.       x = y;
  148.     else
  149.     {
  150.       x = y % mod;
  151.       if (x < 0)
  152.         x += mod;
  153.     }
  154.   }
  155.   mint operator-() { return mint(-x + mod); }
  156.   mint operator~() const
  157.   {
  158.     ll a, b;
  159.     extgcd(x, mod, a, b);
  160.     return a;
  161.   }
  162.   mint &operator+=(const mint &a)
  163.   {
  164.     if ((x += a.x) >= mod)
  165.       x -= mod;
  166.     return *this;
  167.   }
  168.   mint &operator-=(const mint &a)
  169.   {
  170.     if ((x -= a.x) < 0)
  171.       x += mod;
  172.     return *this;
  173.   }
  174.   mint &operator*=(const mint &a)
  175.   {
  176.     x = (x * a.x) % mod;
  177.     return *this;
  178.   }
  179.   mint &operator/=(const mint &a)
  180.   {
  181.     this->operator*=(~a);
  182.     return *this;
  183.   }
  184.   mint operator++()
  185.   {
  186.     ++x;
  187.     if (x == mod)
  188.       x = 0;
  189.     return (*this);
  190.   }
  191.   mint operator++(int)
  192.   {
  193.     x++;
  194.     if (x == mod)
  195.       x = 0;
  196.     return mint(x - 1);
  197.   }
  198.   mint operator--()
  199.   {
  200.     --x;
  201.     if (x == -1)
  202.       x = mod - 1;
  203.     return (*this);
  204.   }
  205.   mint operator--(int)
  206.   {
  207.     x--;
  208.     if (x == -1)
  209.       x = mod - 1;
  210.     return mint(x + 1);
  211.   }
  212.   mint pow(ll b) const
  213.   {
  214.     mint res(1);
  215.     mint a(*this);
  216.     while (b)
  217.     {
  218.       if (b & 1)
  219.         res *= a;
  220.       a *= a;
  221.       b >>= 1;
  222.     }
  223.     return res;
  224.   }
  225.   mint operator+(const mint &a) const { return mint(*this) += a; }
  226.   mint operator-(const mint &a) const { return mint(*this) -= a; }
  227.   mint operator*(const mint &a) const { return mint(*this) *= a; }
  228.   mint operator/(const mint &a) const { return mint(*this) /= a; }
  229.   bool operator<(const mint &a) const { return x < a.x; }
  230.   bool operator<=(const mint &a) const { return x <= a.x; }
  231.   bool operator>(const mint &a) const { return x > a.x; }
  232.   bool operator>=(const mint &a) const { return x >= a.x; }
  233.   bool operator==(const mint &a) const { return x == a.x; }
  234.   bool operator!=(const mint &a) const { return x != a.x; }
  235.  
  236.   friend istream &operator>>(istream &is, mint p) { return is >> p.x; }
  237.   friend ostream &operator<<(ostream &os, mint p) { return os << p.x; }
  238. };
  239.  
  240. /*----------------------------mint_stuff----------------------------*/
  241.  
  242. ll gcd(ll a, ll b)
  243. {
  244.   if (a == 0)
  245.     return b;
  246.   ll r = b % a;
  247.   if (r == 0)
  248.     return a;
  249.   else
  250.     return gcd(r, a);
  251. }
  252.  
  253. long long nCr(int n, int r, int M)
  254. {
  255.   if (r > n - r)
  256.     r = n - r;
  257.   long long ans = 1;
  258.   int i;
  259.  
  260.   for (i = 1; i <= r; i++)
  261.   {
  262.     ans *= n - r + i;
  263.     ans /= i;
  264.   }
  265.   return ans;
  266. }
  267. ll binPow(ll a, ll b, ll m)
  268. {
  269.   a %= m;
  270.   ll ans = 1;
  271.   while (b != 0)
  272.   {
  273.     if (b & 1)
  274.       ans = (ans * a) % m;
  275.     a = (a * a) % m;
  276.     b = b >> 1;
  277.   }
  278.   // O(log2(k))
  279.   return ans;
  280. }
  281.  
  282. ll binMul(ll n, ll k, ll m)
  283. {
  284.   ll ans = 0;
  285.   while (k != 0)
  286.   {
  287.     if (k & 1)
  288.       ans = (ans + n) % m;
  289.     n = (2 * n) % m;
  290.     k = k >> 1;
  291.   } // O(log2(k))
  292.   return ans;
  293. }
  294.  
  295. /*modInverse: binPow(n,M-2,M)*/
  296. /*For very large Expo, use b=b%(M-1),where M is a prime number and a^b%M is req*/
  297. /*---------------------------------- NUMBER THEORY--------------------------------*/
  298. // ll toBase9(ll n){
  299.  
  300. // }
  301. int main()
  302. {
  303.   ios_base::sync_with_stdio(false);
  304.   cin.tie(NULL);
  305. #ifndef ONLINE_JUDGE
  306.   freopen("inputf.in", "r", stdin);
  307.   freopen("outputf.in", "w", stdout);
  308.   freopen("debug.txt", "w", stderr);
  309. #endif
  310.   int ttt = 1;
  311.   // ll zz = -1;
  312.   // cin >> ttt;
  313.   while (ttt--)
  314.   {
  315.     cout << setprecision(30);
  316.     map<ll, ll> mp, cnt;
  317.     ll n, max = 0, orig, min = INF, sum = 0, f = 0;
  318.     cin >> n;
  319.     // n =  ttt;
  320.     // cout <<"n"<< n << nl;
  321.     ll ans = 0;
  322.     vll v;
  323.     orig = n;
  324.     // assert(n != -1);
  325.     while (n / 9 != 0)
  326.     {
  327.       // cout << n << nl;
  328.       v.pb(n % 9);
  329.       n /= 9;
  330.     }
  331.     if (n % 9 != 0)
  332.       v.pb(n % 9);
  333.     // reverse(all(v));
  334.     // pvec(v);
  335.     ll z = 0;
  336.     ll x = 0;
  337.     for (auto p : v)
  338.     {
  339.       x += p;
  340.       // if(p==0){
  341.       //     z++;
  342.       //     conti
  343.       // }
  344.       ll p9 = (ll)pow(9, z);                               //
  345.       ans += (((((p * (p - 1)) / 2) % 4) * (p9 % 4))) % 4; //
  346.  
  347.       ans += ((p % 4) * ((orig % (p9) + 1) % 4)) % 4;
  348.       // cout << (p9*9) << nl;
  349.       // sum += ((p+1) * p9) % 4;
  350.       z++;
  351.     }
  352.     cout << (ans) % 4 << nl;
  353.     // if ((zz != ans % 4)&&zz!=-1)
  354.     // {
  355.     //   no return 0;
  356.     // }
  357.     // zz = (4 + (ans - x) % 4) % 4;
  358.   }
  359.   return 0;
  360. }
  361.  
  362. /*
  363. 1. Always be cautious of 'n==1 and n==2' in Number theory Ques.
  364. 2. Always treat your edge cases distinctly, never try to indulge them in usual loops!
  365. 3. Always check back and forth for equality cases!
  366. 4. always add a break after f++;
  367. 5. always sort before using upper_bound
  368. 6. any changing DS is best declared as global and cleared after each test case!
  369. 7. Don't overthink, at first just try to go for the simplemost approach, use Implementations.md for reference!
  370. */
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/pztfko
language:
C++14 (clang 8.0)
created:
1 year ago
visibility:
secret

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!