fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define nl '\n'
  5.  
  6. inline ll mulmod(ll a, ll b, ll m) {
  7.     return (__int128)a * b % m;
  8. }
  9.  
  10. inline ll powmod(ll a, ll b, ll m) {
  11.     ll res = 1;
  12.     while (b) {
  13.         if (b & 1) res = mulmod(res, a, m);
  14.         a = mulmod(a, a, m);
  15.         b >>= 1;
  16.     }
  17.     return res;
  18. }
  19.  
  20. inline ll numlen(ll x) {
  21.     ll c = 0;
  22.     do { ++c; x /= 10; } while (x);
  23.     return c;
  24. }
  25.  
  26. int main() {
  27.     ios::sync_with_stdio(false);
  28.     cin.tie(nullptr);
  29.  
  30.     int T;
  31.     cin >> T;
  32.     while (T--) {
  33.         ll x, n, m;
  34.         cin >> x >> n >> m;
  35.         ll len[64], t[64];
  36.         len[0] = powmod(10, numlen(x), m);
  37.         t[0] = x % m;
  38.  
  39.         for (int i = 1; i < 63; ++i) {
  40.             len[i] = mulmod(len[i-1], len[i-1], m);
  41.             t[i] = mulmod(t[i-1], (len[i-1] + 1) % m, m);
  42.         }
  43.  
  44.         ll ans = 0;
  45.         for (int i = 62; i >= 0; --i)
  46.             if ((n >> i) & 1)
  47.                 ans = (mulmod(ans, len[i], m) + t[i]) % m;
  48.  
  49.         cout << ans << nl;
  50.     }
  51. }
  52.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3
1234 3 9
6 100 8
123456789 999999999999999999 9876543210
stdout
copy 
3
2
5152901139
https://ideone.com/EMApaT
language:
C++14 (gcc 8.3)
created:
12 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!