//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "二次剩余": {
        "prefix": "acm-7.1mi",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "int n,T,P,W,det;",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "inline int mi(Re x,Re k){",
            "\tRe s=1;",
            "\twhile(k){",
            "\t\tif(k&1)s=(LL)s*x%P;",
            "\t\tx=(LL)x*x%P,k>>=1;",
            "\t}",
            "\treturn s;",
            "}",
            "struct CP{",
            "\tint x,y;CP(Re X=0,Re Y=0){x=X,y=Y;}",
            "\tinline CP operator*(const CP &O)const{return CP(((LL)x*O.x%P+(LL)y*O.y%P*W%P)%P,((LL)x*O.y%P+(LL)y*O.x%P)%P);}",
            "\tinline CP operator*=(const CP &O){return *this=*this*O;}",
            "};",
            "inline CP mi_(CP x,Re k){",
            "\tCP s=CP(1,0);",
            "\twhile(k){",
            "\t\tif(k&1)s*=x;",
            "\t\tx*=x,k>>=1;",
            "\t}",
            "\treturn s;",
            "}",
            "inline LL Sqrt(Re n){",
            "    if(!n)return 0;Re x;",
            "    while(1){",
            "        x=rand()%P,W=((LL)x*x%P-n+P)%P;",
            "        if(mi(W,(P-1)/2)==P-1)break;",
            "    }",
            "    return mi_(CP(x,1),(P+1)/2).x;",
            "}",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(T);",
            "\twhile(T--){",
            "\t\tin(n),in(P);",
            "\t\tif(mi(n,(P-1)/2)==P-1)puts(\"Hola!\");//�޽�",
            "\t    else{",
            "\t\t    det=Sqrt(n);",
            "\t\t    if(det)printf(\"%d %d\\n\",min(det,P-det),max(det,P-det));",
            "\t\t    else printf(\"%d\\n\",det);",
            "\t\t}",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 二次剩余"
    }
}