fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. #define all(x)  x.begin(),x.end()
  11. #define v(x) vector<x>
  12. #define nl '\n'
  13. #define fxd(x) fixed << setprecision(x)
  14. template<class t> using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  15. template<class t> using ordered_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;
  16.  
  17.  
  18. ll extGCD(ll a, ll b, ll &x, ll &y) {
  19.     if (b == 0) {
  20.         x = 1;
  21.         y = 0;
  22.         return a;
  23.     }
  24.     ll x1, y1;
  25.     ll d = extGCD(b, a % b, x1, y1);
  26.     x = y1;
  27.     y = x1 - y1 * (a / b);
  28.     return d;
  29. }
  30.  
  31. ll modInverse(ll A, ll M) {
  32.     ll x, y;
  33.     ll g = extGCD(A, M, x, y);
  34.  
  35.     if (g != 1) {
  36.         return -1;
  37.     } 
  38.     else {
  39.         return (x % M + M) % M;
  40.     }
  41. }
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  45.     ll n , m; cin >> n >> m;
  46.     ll minv = modInverse(n,m);
  47.     if(minv == -1)
  48.     {
  49.         cout << "No such integer exists.";
  50.     }
  51.     else
  52.     {
  53.         cout << minv;
  54.     }
  55. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No such integer exists.
https://ideone.com/0jMIJ3
language:
C++ (gcc 8.3)
created:
1 hour 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!