fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sz(o) ((int)o.size())
  5. #define all(o) o.begin(), o.end()
  6. #define rep(i, a, b) for(int i = (a); i <= (b); i++)
  7. #define repr(i, a, b) for(int i = (a); i >= (b); i--)
  8. #define INF 1000000000000000000LL
  9. #define MOD 1000000007
  10. #define EPS 1e-9
  11. #define PI 3.1415926535
  12. #define ff first
  13. #define ss second
  14. typedef long long int ll;
  15. typedef vector<ll> vll;
  16. typedef vector<int> vi;
  17. typedef pair<int, int> pi;
  18. typedef pair<ll, ll> pll;
  19. typedef vector<pll> vpll;
  20. typedef vector<pi> vpi;
  21.  
  22. class SimpleMathProblem{
  23. public:
  24.  
  25.     map<int, int> factorize(int n){
  26.         map<int, int> res;
  27.         for(ll i = 2; i * i <= n; i++){
  28.             while(n % i == 0){
  29.                 res[i]++;
  30.                 n /= i;
  31.             }
  32.         }
  33.         if(n > 1) res[n]++;
  34.         return res;
  35.     }
  36.  
  37.     int phi(int n){
  38.         map<int, int> factors = factorize(n);
  39.         int res = n;
  40.         for(auto p : factors){
  41.             res *= (p.ff - 1);
  42.             res /= p.ff;
  43.         }
  44.         return res;
  45.     }
  46.  
  47.     int bpow(int a, int b, int m){
  48.         int res = 1;
  49.         while(b > 0){
  50.             if(b & 1) res = (int)((res * 1LL * a) % m);
  51.             a = (int)((a * 1LL * a) % m);
  52.             b >>= 1;
  53.         }
  54.         return res;
  55.     }
  56.  
  57.  
  58.     int calculate(int a, int b, int c, int m){
  59.         map<int, int> factors = factorize(m);
  60.         int ans = 0;
  61.         vector<pair<int, pi>> v;
  62.         for(auto p : factors){
  63.             int mod = (int)pow(p.ff, p.ss);
  64.             if(a % p.ff != 0){
  65.                 int x = bpow(b, c, phi(mod));
  66.                 int ci = bpow(a, x, mod);
  67.                 int N = m / mod;
  68.                 int invN = bpow(N, mod-2, mod);
  69.                 v.push_back({ci, {N, invN}});
  70.             }
  71.         }
  72.         for(auto p : v){
  73.             ans += (int)((((p.ff * 1LL * p.ss.ff) % m) * 1LL * p.ss.ss) % m);
  74.             ans %= m;
  75.         }
  76.         return ans;
  77.     }
  78. };
  79.  
  80. void solve(int testcase){
  81.     SimpleMathProblem *obj = new SimpleMathProblem();
  82.     cout << obj->calculate(3737373, 7373737, 37373, 737373737);
  83. }
  84.  
  85. int main() {
  86.     #ifdef VPAL
  87.     freopen("in.txt", "r", stdin);
  88.     freopen("out.txt", "w", stdout);
  89.     #endif
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(NULL);
  92.     cout.tie(NULL);
  93.     cout << fixed << setprecision(20);
  94.     clock_t b = clock();
  95.     int t = 1;
  96.     //cin >> t;
  97.     rep(tt, 1, t) solve(tt);
  98.     clock_t e = clock();
  99.     cerr << (double(e - b) / CLOCKS_PER_SEC) << " sec";
  100.     return 0;
  101. }
  102.  
Success #stdin #stdout #stderr 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
46078129
stderr
copy 
6e-05 sec
https://ideone.com/yBEjmJ
language:
C++14 (gcc 8.3)
created:
6 years 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!