fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define file(NAME) if (fopen(NAME".inp", "r"))  freopen(NAME".inp", "r", stdin), freopen(NAME".out", "w", stdout)
  6. #define FOR(i, a, b) for (int i = (int) a; i <= (int) b; ++i)
  7. #define FOD(i, a, b) for (int i = (int) a; i >= (int) b; --i)
  8.  
  9. #define all(s) (s).begin(), (s).end()
  10. #define pb push_back
  11. #define ll long long
  12. #define fi first
  13. #define se second
  14. #define pii pair<int, int>
  15.  
  16. const int maxn = 1e5 + 5;
  17. const int N = 505;
  18. const int MOD = 1e9 + 7;
  19.  
  20.  
  21.  
  22. int x, v, n;
  23.  
  24. int change(int n) {
  25.     if (!n) return 0;
  26.     return ((n % 10) * (n % 10) + change(n / 10));
  27. }
  28.  
  29.  
  30.  
  31. void solve() {
  32.     cin >> x >> v >> n;
  33.  
  34.  
  35.     vector<int> circle;
  36.     unordered_map<int, int> freq, freq1;
  37.     while (true) {
  38.         freq[x]++;
  39.         // cerr << x << ' ';
  40.         circle.pb(x);
  41.         if (freq[x] == 2) break;
  42.         x = change(x);
  43.     }
  44.  
  45.     int cur = 0;
  46.     vector<int> tmp;
  47.     for (int i = 0; i < circle.size(); ++i) {
  48.         if (freq[circle[i]] == 2) {
  49.             --freq[circle[i]];
  50.             cur = i; break;
  51.         }
  52.         tmp.pb(circle[i]);
  53.         --freq[circle[i]];
  54.         ++freq1[circle[i]];
  55.     }
  56.  
  57.     int len2 = circle.size() - 1 - cur;
  58.  
  59.  
  60.     int len1 = tmp.size();
  61.  
  62.  
  63.  
  64.     ll ans = 0;
  65.     if (n <= len1) {
  66.         if (freq1[v] == 0) ans = 0;
  67.         else for (int i = 0; i < n; ++i) {
  68.             if (tmp[i] == v) {
  69.                 ans = 1; break;
  70.             }
  71.         }
  72.     }
  73.     else {
  74.         n -= len1;
  75.         ans += freq1[v];
  76.  
  77.         ans += (freq[v] * (n / len2));
  78.  
  79.         FOR(i, cur, cur + (n % len2) - 1) {
  80.             if (circle[i] == v) {
  81.                 ++ans; break;
  82.             }
  83.         }
  84.     }
  85.  
  86.  
  87.  
  88.     cout << ans << '\n';
  89. }
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97. int Test;
  98. signed main() {
  99.     cin.tie(0) -> sync_with_stdio(0);
  100.     file("x");
  101.  
  102.  
  103.  
  104.     cin >> Test;
  105.     while (Test--) solve();
  106.  
  107.     return 0;
  108. }
  109.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NEDarB
language:
C++14 (gcc 8.3)
created:
4 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!