Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- using namespace std;
- ifstream fin("inversmodular.in");
- ofstream fout("inversmodular.out");
- int gcdExtended(int a, int n, int &x, int &y)
- {
- if(a == 0)
- {
- x = 0;
- y = 1;
- return n;
- }
- int x1, y1;
- int gcd = gcdExtended(n % a, a, x1, y1);
- x = y1 - x1 * (n / a);
- y = x1;
- return gcd;
- }
- int modInv(int a, int n)
- {
- int x, y;
- int gcd = gcdExtended(a, n, x, y);
- if(gcd != 1)
- return -1;
- else
- return (1ll * x + n) % n;
- }
- int main()
- {
- int a, n;
- fin >> a >> n;
- fout << modInv(a, n) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement