fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. #define int long long // câu thần chú :>
  5.  
  6. typedef long long ll;   
  7.  
  8. /* Riêng ở bài này các em nhớ chú ý đến giới hạn của đề bài, các số đều <= 1e18.
  9.    Thì phép nhân 2 số trong trường hợp này rất nhạy cảm :<
  10.    Ví dụ như MOD = 1e18, thì phép nhân 2 số tuy đã áp dụng công thức vẫn có thể bị tràn 
  11.    Ví dụ như a = b = 1e18 - 1, MOD = 1e18
  12.    thì a % MOD, b % MOD vẫn = 1e18 - 1, nên khi nhân lại thì ~ 1e36, trong khi long long tối đa chỉ có ~ 9e18.
  13.    nên ở bài này chúng ta sẽ viết lại hàm mul(a, b) bằng thuật toán sau (dùng ý tưởng tương tự như ở thuật tính a^b): 
  14.    chính là ta sẽ phân tích b sang hệ nhị phân, b = 2^i0 + 2^i1 + 2^i2 + ... + 2^ik 
  15.    thì a * b = a * (2^i0 + 2^i1 + 2^i2 + ... + 2^ik)
  16.              = a * 2^i0 + a * 2^i1 + a * 2^i2 + a * 2^ik   
  17.    Ví dụ 3 * 5 = 3 * (101_2) = 3 * (2^2 + 2^0) = 3 * 2^2 + 3 * 2^0  
  18.    Thì các em thấy rằng với việc này giống như ta phân rã b ra thành những b_i nhỏ hơn 
  19.    để khi nhân a vào sẽ tránh được lỗi tràn số. 
  20. */
  21.  
  22. ll MOD;   
  23.  
  24. int mul(int a, int b) {
  25.     int ans = 0;  
  26.     for (; b > 0; b >>= 1) {
  27.         if (b & 1) ans = (ans + a) % MOD;  
  28.         a = (a + a) % MOD;  
  29.     }
  30.     return ans;  
  31. }
  32.  
  33. int binpow(int a, int b) {
  34.     int ans = 1;  
  35.     for (; b > 0; b >>= 1) {
  36.         if (b & 1) ans = mul(ans, a); // ans * a % MOD;  
  37.         a = mul(a, a); // a * a % MOD; 
  38.     }
  39.     return ans; 
  40. }
  41.  
  42. signed main() {
  43.     ios::sync_with_stdio(0); cin.tie(0); 
  44.     ll x, y, n;  
  45.     cin >> x >> y >> n >> MOD;    
  46.  
  47.     ll ans = binpow(x, n) - binpow(y, n);     
  48.     ans = (ans + MOD) % MOD; 
  49.  
  50.     cout << ans << '\n';   
  51.  
  52.     return 0;  
  53. }
  54.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
3 2 4 3
stdout
copy 
2
https://ideone.com/DG6DBT
language:
C++14 (gcc 8.3)
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!