Cách tính a*b mod m , a^b mod m , a^(-1) mod m với m không phải là số nguyên tố (inversion có nghĩa khi (a,m)=1)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD (ll)(1000000000000000009)
ll inv(ll a, ll mod){
  ll r = mod;
  ll nr = a;
  ll t = 0;
  ll nt = 1;
  ll tmp;
  while(nr!=0){
     ll q = r/nr;
     tmp = nt; nt = t - q*nt; t = tmp;
     tmp = nr; nr = r - q*nr; r = tmp;
  }
  if (r > 1) return -1; // no inverse
    if (t < 0) t += mod;
    return t;
}
ll f(ll a,ll n, ll mod){
  ll res = a, ans =0;
  while(n){
    if(n%2) ans = (ans + res ) %mod;
    res = (res + res)%mod;
    n/=2;
  }
  return ans;
}
ll po(ll a,ll n, ll mod){
  ll res = a, ans =1;
  while(n){
    if(n%2) ans = f(ans,res,mod);
    res = f(res,res,mod);
    n/=2;
  }
  return ans;
}
int main(){
  ll x,y,z,m,dem=0,res1,res2,res,tmp=1;
  cin>>x>>y>>z>>m;
  if(x==1) {cout<<1;return 0;}
  res1 = po(x,y,m);
  res2 = inv(z,m);
  res = f(res1,res2,m);
  //ll res = inv(2,3);
  cout<<res;
}