Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của RR

//Written by Nguyen Thanh Trung
//Tai lieu tham khao: Sqrt Mod P - Ngo Minh Duc
//Shanks-Tonelli's algorithm
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
var
  x,a,p:longint;
  test:longint;
  f1,f2:text;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
function Legrende(a,n:longint):int64; //The only function that I don't understand :(
var
  e,s:int64;
begin
  if a<=1 then Legrende:=a
  else
    begin
      e:=0;
      while a and 1=0 do
        begin
          inc(e);
          a:=a>>1;
        end;
      if e and %1=0 then s:=1
      else if (n and %111=1) or (n and %111=7) then s:=1
      else if (n and %111=5) or (n and %111=3) then s:=-1;
      if (n and %11=3) and (a and %11=3) then s:=-s;
      if a=1 then Legrende:=s else Legrende:=s*Legrende(n mod a,a);
    end;
end;
function lt(a,k:longint):longint; //Tinh a^k (mod p)
var
  temp:longint;
begin
  if k and %1=0 then temp:=1 else temp:=a;
  k:=k>>1;
  while (k>0) do
    begin
      a:=(int64(a)*a) mod p;
      if k and %1=1 then temp:=(int64(a)*temp) mod p;
      k:=k>>1;
    end;
  exit(temp);
end;
function ord(b:longint):longint;
var
  kq:longint;
begin
  kq:=0;
  while b<>1 do
    begin
      b:=(int64(b)*b) mod p;
      inc(kq);
    end;
  exit(kq);
end;
procedure solve;
var
  c,z,m,k,kk,b,x,xx:longint;
begin
  if Legrende(a,p)=-1 then begin writeln(f2,'Khong co'); exit; end;
  //Dat p-1=2^k*m (m le)
  m:=p-1; k:=0;
  while m and %1=0 do
    begin
      k+=1;
      m:=m>>1;
    end;
  //Chon x=2^((m+1)/2)
  x:=lt(a,(m+1)>>1);
  b:=lt(a,m);
  if b=1 then
    begin
      xx:=-x+p;
      if x<xx then writeln(f2,x,' ',xx)
      else writeln(f2,xx,' ',x);
      exit;
    end;
  //Chon z ngau nhien sao cho z la non-residue
  repeat
    z:=random(p-1)+1;
  until Legrende(z,p)=-1;
  c:=lt(z,m);
  repeat
    kk:=ord(b);
    x:=(lt(c,1<<(k-kk-1))*x) mod p;
    b:=(lt(c,1<<(k-kk))*b) mod p;
  until b=1;
  xx:=-x+p;
  if x<xx then writeln(f2,x,' ',xx)
  else writeln(f2,xx,' ',x);
end;
begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      read(f1,a,p); a:=a mod p;
      if p=2 then
        begin
          if a=1 then writeln(f2,1) //Xet rieng TH p=2
          else writeln(f2,'Khong co');
        end
      else solve; //Shanks-Tonelli's algorithm
    end;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
typedef long long ll;

ll a,n,mu2[50];

long long mu(ll u,ll k)
{
      if(k==1)
          return u;
      else
      {
          ll t = mu(u,k/2);
          if(k%2==0)
               return (t*t)%n;
          else return (t*t*u)%n;
      }
}

ll xuly(ll a,ll p)
{
     if(a%n==0)
         return 0;
     if(mu(a,(p-1)/2)!=1)
         return -1;
     ll m = p-1,k=0,z,c,kk,the;
     while(m%2==0){k++;m/=2;}
     ll x = mu(a,(m+1)/2), b = mu(a,m);
     if(b==1) return x;
     the = b;
     for(z=2;;z++) {if(mu(z,(p-1)/2)==p-1) break;}
     c = mu(z,m);
     while(b!=1)
     {
          the = b,kk=0;
          while(the!=1) {kk++; the=(the*the)%p;}
          x = (mu(c,mu2[k-kk-1])*x)%p;
          b = (mu(c,mu2[k-kk])*b)%p;          
     }
     return x;
}

int main()
{
    mu2[0] = 1; for(int i = 1;i<=40;i++) mu2[i] = mu2[i-1]*2;
    int test;
    scanf("%d",&test);
    for(int itest=0;itest<test;itest++){
            scanf("%lld %lld",&a,&n);
            a = a%n;
            if(a%n==0)
                  printf("0\n");
            else if(n==2)
                printf("1\n");
            else
            {
                long long x = xuly(a,n);
                long long y = n-x;
                if(x==-1)
                     printf("Khong co\n");
                else 
                {
                     if(x>y)
                     {
                            long long temp = x;
                            x = y;
                            y = temp;
                     }
                     printf("%lld %lld\n",x,y);
                }
            }
    }
   // getch();
}

Code mẫu của ll931110

//#pragma comment(linker, "/STACK:16777216")
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

int a,p,T;

int gen(int x)
{
    double slope = 1.0 * rand()/RAND_MAX;
    return (int) trunc(slope * x);
}

int power(int x,int v)
{
    if (!v) return 1;
    int q = power(x,v/2);
    q = (q * q) % p;
    if (v & 1) q = (q * x) % p;
    return q;
}

int Legrende(int x)
{
    return power(x,(p - 1)/2);
}

int main()
{
//    freopen("root.in","r",stdin);
//    freopen("root.ou","w",stdout);
    scanf("%d", &T);
    srand(time(NULL));
    while (T--)
    {
        scanf("%d %d", &a, &p);
        if (p == 2)
        {
            printf("1\n");  continue;
        }
        if (Legrende(a) == p - 1)
        {
            printf("Khong co\n");  continue;
        }
        int b;
        while (1)
        {
            b = gen(p);  
            if (!b) continue;
            if (Legrende(b) == p - 1) break;
        }

        int s = 0,t = p - 1;
        while ( (t & 1) == 0)
        {
            t >>= 1;  s++;
        }

        int r = power(a,(t + 1)/2),c = power(b,t),inv = power(a,p - 2);
        for (int i = 1; i < s; i++)
        {
            int d = (((r * r) % p) * inv) % p; 
            d = power(d,1 << (s - i - 1));
            if (d == p - 1) r = (r * c) % p;
            c = (c * c) % p;
        }
        int p1 = r,p2 = p - r;
        if (p1 > p2) swap(p1,p2);
        printf("%d %d\n", p1, p2);
    }
}

Code mẫu của khuc_tuan

#include "stdio.h"
#include "algorithm"

using namespace std;

#define FI first
#define SE second

typedef int kint;

#define int long long

typedef pair<int,int> PII;

int gcd(int a,int b) {
    while(a!=0 && b!=0) {
        if(a<b) b%=a;
        else a%=b;
    }
    return a+b;
}

PII Exgcd(int a,int b) {
    if(a==1) return PII(b+1,-1);
    if(b==1) return PII(-1,a+1);
    bool d=false;
    if(a>b) a^=b, b^=a, a^=b, d=true;
    PII r = Exgcd(a,b%a);
    int t = r.FI/b;
    r.FI -= t*b;
    r.SE += t*a;
    if(!d) return PII(r.FI-r.SE*(b-b%a)/a,r.SE);
    else return PII(r.SE, r.FI-r.SE*(b-b%a)/a);
}

int Jacobi(int a,int n) {
    //printf("%I64d %I64d", a, n);
    if(a==0) return 0;
    if(a==1) return 1;
    int e=0, a1=a, s, n1;
    while(a1%2==0) { a1/=2; ++e; }
    if(e%2==0 || n%8==1 || n%8==7) s=1;
    else s=-1;
    if(n%4==3 and a1%4==3) s=-s;
    n1 = n % a1;
    if(a1==1) return s;
    else return s * Jacobi(n1, a1);
}

int tinhdu(int cs, int mu, int mod) {
    if(mu==0) return 1;
    if(mu==1) return cs%mod;
    int t = tinhdu(cs, mu/2, mod);
    if(mu%2==0) return t*t%mod;
    else return t*t%mod*cs%mod;
}

kint main() {
    int st, a, p, b, s, t, a_1, c, r;
    scanf("%lld",&st);
    while(st--) {
        scanf("%lld%lld", &a, &p);
        a %= p;
        if(p==2) {
            printf("1\n");
        }
        else if(Jacobi(a,p)==-1) {
            printf("Khong co\n");
        }
        else {
            if(p%4==3) {
                r = tinhdu(a, (p+1)/4, p);
            }
            else if(p%8==5) {
                int d = tinhdu(a, (p-1)/4, p);
                if(d==1) r = tinhdu(a, (p+3)/8, p);
                else r = 2 * a * tinhdu(4*a%p, (p-5)/8, p) % p;
            }
            else {
                do {
                    b = rand()%(p-1) + 1;
                } while(Jacobi(b,p)!=-1);
                //printf("ok %lld ", b);
                t = p-1;
                s = 0;
                while(t%2==0) { t/=2; ++s; }
                a_1 = Exgcd(a,p).FI;
                //printf("asdasd %lld %lld",a_1, Exgcd(a,p).SE);
                a_1 %= p;
                if(a_1<0) a_1+=p;
                c = tinhdu(b, t, p);
                r = tinhdu(a, (t+1)/2, p);
                int mm = 1;
                for(int i=0;i<s-2;++i) mm*=2;
                for(int i=1;i<=s-1;++i) {
                    int d = tinhdu(r*r*a_1 % p, mm, p);
                    if(d == p-1 || d==-1) r = r*c % p;
                    c = c*c%p;
                    mm /= 2;
                }
            }       
            if(r*r%p != a) printf("Sai\n");
            if(r<p-r) printf("%lld %lld\n", r, p-r);
            else printf("%lld %lld\n", p-r, r);
        }
    }
    return 0;
}