• 1.费马定理
  • 择出来模是质数的时候对应的答案
• 2.快速幂i应用
• 3.

🍿code_main

```cpp

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef long long LL;

LL qmi(int a, int b, int p)
{
LL res = 1;
while (b)
{
if (b & 1) res = res * a % p;
a = a * (LL)a % p;
b >>= 1;
}
return res;
}

int main()
{
int n;
scanf(“%d”, &n);
while (n – )
{
int a, p;
scanf(“%d%d”, &a, &p);
if (a % p == 0) puts(“impossible”);
else printf(“%lld\n”, qmi(a, p - 2, p));
}

return 0;

}
```

🦄算法步骤

• 1.
• 2.
• 3.