Обратное число

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    long long p,a;
    long long b;
    for(int i = 0; i<t;i++){
        cin>>p>>a;
        b = pow(a,p - 2);
        cout << b % p << endl;
    }
    return 0;
}

#include <iostream>
#include <string>
 
using namespace std;
 
int f(int p, int a)
{
    for (int i = 1;i < p;i++){
        if ((i * a - 1) % p == 0){
            return i;
        }
    }
}
 
int main()
{
    int t;
    cin >> t;
    string s = "";
    for(int i = 0; i < t;i++){
        int p,a;
        cin >> p >> a;
        s += to_string(f(p,a));
    }
    for (int i = 0; i < s.size();i++){
        cout << s[i] << endl;
    }
    return 0;
}

#include <cstdio>
#include <cassert>
 
unsigned foo(unsigned p, unsigned a)
{
  assert(a && a < p);
 
  for (unsigned b = 1, n = 1; b < p; n++)
  {
    b = (p * n + 1) / a;
    if (!((p * n + 1) % a)) return b;
  };
 
  return 0;
}
 
int main(void)
{
  // 2 ≤ p ≤ 10^9, 0 < a < p
  struct { unsigned p, a; } x[] = {{17, 4}, {29, 11}, {2203, 113}, {3559, 250}, {0, 0}};
 
  // тестирование функции
  for (auto ptr = x; ptr->a; ptr++)
  {
    unsigned b = foo(ptr->p, ptr->a);
    printf("p = %u; a = %u; b = %u; ab - 1 = %u\n", ptr->p, ptr->a, b, ptr->a * b - 1);
  }
 
  getchar();
  return 0;
}

#include <iostream>
#include <cmath>
 
using namespace std;
 
 
long long binpow(long long a,long long n,long long p) {
 
    if(!n)return 1;
    if(n % 2)return ((binpow(a,n-1,p) * a)%p);
    else{
        long long b = (binpow(a, n/2,p))%p;
        return ((b * b)%p);
    }
}
 
 
int main()
{
    long long t;
    cin >> t;
    for(long long i = 0;i < t;i++){
        long long p,a;
        cin >> p >> a;
        cout << binpow(a,p-2,p) << endl;
    }
}