【BZOJ 3884】拓展歐拉定理

1.​​題目連結​​。看到這個題目就覺得自己是個沙雕，省賽的時候上來看到這個類似的題目我就記得我做過，或者在哪看過來着。但是死活沒有想起來，最後回來寫這個題的時候弄了好半天。當時有點緊張了。忘了一些東西。

2.我們知道，對于

取模當gcd(a,mod)=1的時候我們可以直接在指數上取模，但是當gcd（a,mod)!=1的時候，我們也是可以繼續取模的。這個東西叫做拓展歐拉定理。

#include<bits/stdc++.h>
using namespace std;
#pragma warning(disable:4996)
#define ll long long
ll Euler(ll n)
{
  ll ans = n;
  ll tmp = sqrt(n);
  for (int i = 2; i <= tmp; i++)
  {
    if (n%i == 0)
    {
      ans -= ans / i;
      while (n%i == 0)
        n /= i;
    }
  }
  if (n > 1)
    ans -= ans / n;
  return ans;
}
ll qpow(ll a, ll b,ll p)
{
  ll ans = 1;
  while (b)
  {
    if (b & 1)
      ans = ans * a%p;
    a = a * a%p;
    b >>= 1;
  }
  return  ans;
}
ll solve(ll p)
{
  if (p == 2 || p == 1)return 0;
  ll tmp = Euler(p);
  return qpow(2, solve(tmp) + tmp, p);
}
int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
    ll p;
    scanf("%lld", &p);
    printf("%lld\n", solve(p));
  }
  return 0;
}