。

类似fft，自定义一种复数，使得第二维的平方等于w。

然后就可以进行SAO操作了。

注意sgn要返回long long

例题：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 typedef long long LL; 6 const int N = 100010; 7  8 LL w, MO; 9 10 inline int rd() {11     return (rand() * (1ll << 16) + rand()) % LONG_MAX;12 }13 14 struct cp {15     LL x, y;16     cp(LL X = 0, LL Y = 0) {17         x = X;18         y = Y;19     }20     inline cp operator *(const cp &W) const {21         return cp(x * W.x % MO + y * W.y % MO * w % MO, x * W.y % MO + y * W.x % MO);22     }23     inline cp operator %(const LL &W) const {24         return cp(x % W, y % W);25     }26 };27 28 template 
         
           inline T qpow(T a, LL b) {29     T ans(1);30     while(b) {31         if(b & 1) ans = ans * a % MO;32         a = a * a % MO;33         b = b >> 1;34     }35     return ans;36 }37 38 inline int sgn(LL x) {39     return qpow(x, (MO - 1) >> 1);40 }41 42 inline void solve() {43     LL n;44     scanf("%lld%lld", &n, &MO);45     n %= MO;46     if(MO == 2) {47         printf("%d\n", n);48         return;49     }50     if(sgn(n) == MO - 1) {51         printf("No root\n");52         return;53     }54     LL a;55     while(1) {56         a = rd() % MO;57         w = (a * a % MO - n + MO) % MO;58         if(sgn(w) == MO - 1) break;59     }60     cp ans(a, 1);61     ans = qpow(ans, (MO + 1) >> 1);62     LL b = ans.x, c = MO - b;63     if(b > c) std::swap(b, c);64     printf("%lld %lld \n", b, c);65     return;66 }67 68 int main() {69     srand(19384);70     int T;71     scanf("%d", &T);72     while(T--) solve();73     return 0;74 }