Problems in extended Euclidean inverse element

CSDN Q & A 2022-01-15 02:50:42

When extending Euclidean inverse , The last step x = (x%p + p) % p; How did you get it
#include
#include
#include
using namespace std;
long long x, y, n,p;// It is best to define global variables
inline void exgcd(long long a, long long b)
{
if (b == 0) // When b=0 I met a special solution , You can recursively calculate the answer
{
x = 1, y = 0;
return;
}
exgcd(b, a%b);
long long k;
k = x;
x = y;
y = k - (a / b)*y;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> p;
for (long long i = 1; i <= n; i++) {
exgcd(i, p);
x = (x%p + p) % p;
cout << x << endl;
}
return 0;
}


thank
Similar articles

2022-01-15

2022-01-15