【Codeforces 1091G】New Year and the Factorisation Collaboration
交互题，中国剩余定理
题目大意：
给定正整数 $n$（$21\leq n\leq 2^{1024}$），保证 $n$ 能表示成 $\prod\limits_{i=1}^kp_i$ 的形式，其中 $2\leq k\leq 10$，$p$ 是互不相同的 $4n+3$ 形质数。
交互库提供了模 $n$ 意义下的加法、减法、乘法、求逆、求平方根、乘方操作。其中求逆和求平方根在不存在结果时返回 $-1$，存在多个模意义下的平方根时，只返回其中一个，且多次询问结果不会改变。
最多进行 $100$ 次交互（包括返回答案），要求对 $n$ 分解质因数。
题解：
交互库提供的操作只有 sqrt 是有用的，因为其他操作我们都可以自己轻松地实现。
考虑如何合理利用 sqrt 这个操作。
我们假设知道 $x^2\equiv x’^2\pmod n$，那么就有 $(x+x’)(x-x’)\equiv 0\pmod n$，即 $(x+x’)(x-x’)=nc$。
对于 $(x+x’)$ 和 $(x-x’)$，排除其中有 $0$ 和 $n$ 的情况，则我们可以将 $n$ 的质因子分成两个集合。
假如我们有很多个不同的集合，就可以通过这些集合（中的质因子的乘积）求 $\gcd$ 的方式来提取出 $n$ 的质因子。
交互库提供的这个 sqrt 操作，我们给定 $y$，它可以帮我们找到一个满足 $x^2\equiv y\pmod n$ 的 $x$，而我们需要两个这样的 $x$。那么我们指定一个 $x$，然后向交互库询问 $x^2\bmod n$ 就可以得到另外一个。
不过这样有可能出现两个 $x$ 相同或相反的情况。我们考虑这件事情发生的概率。
由于满足 $x^2-x’^2\equiv 0\pmod n$，那么对于 $i\in[1,k]$，都有 $x^2-x’^2\equiv 0\pmod{p_i}$。
容易证明，在模奇素数意义下，一个数的二次剩余只有 $0$ 个或 $2$ 个，也就是说指定 $x$ 的情况下，有两个 $x’$ 是满足条件的。
由中国剩余定理可以知道，满足 $x^2-x’^2\equiv 0\pmod n$ 的 $x’$ 有 $2^k$ 个，其中有 $2$ 个不能使用，也就是说随机一个 $x$，有 $1-\frac{1}{2^{k-1}}$ 的概率能得到一个符合条件的 $x’$。
那么我们每次询问时随机 $x$ 然后进行上述操作即可。若随机到的 $x$ 与 $n$ 不互质，则直接分成 $\gcd(x,n)$ 和 $\frac n{\gcd(x,n)}$ 即可。
我们可以进行 $99$ 次询问，可以得到足够多的质因子集合，然后提取出所有的质因子即可。
由于涉及高精度运算，使用 Java 或者 Python 会比较方便。
Code：
import java.util.*;
import java.math.*;
public class Main{
static Scanner in=new Scanner(System.in);
static BigInteger n,TWO=BigInteger.valueOf(2);
static BigInteger A[]=new BigInteger[300],B[]=new BigInteger[300];
static int k=0,t=0;
static Random rand=new Random();
static void solve(BigInteger n){
BigInteger x,g,xx,y;
x=new BigInteger(1024,rand);
x=x.remainder(n.subtract(BigInteger.ONE)).add(BigInteger.ONE);
g=n.gcd(x);
if(g.compareTo(BigInteger.ONE)!=0){
A[++k]=g;
A[++k]=n.divide(g);
return;
}
y=x.multiply(x).remainder(n);
System.out.println("sqrt "+y);
System.out.flush();
xx=in.nextBigInteger();
if(x.compareTo(xx)==0||x.add(xx).compareTo(n)==0)return;
x=x.subtract(xx);
if(x.compareTo(BigInteger.ZERO)<0)x.add(n);
g=x.gcd(n);
A[++k]=g;
A[++k]=n.divide(g);
}
public static void main(String args[]){
n=in.nextBigInteger();
A[k=1]=n;
for(int T=0;T<99;++T)solve(n);
for(int i=1;i<=k;++i)
if(A[i].compareTo(BigInteger.ONE)!=0){
BigInteger g=A[i];
for(int j=1;j<=k;++j)
if(A[j].compareTo(BigInteger.ONE)!=0){
BigInteger d=g.gcd(A[j]);
if(d.compareTo(BigInteger.ONE)!=0)
g=d;
}
B[++t]=g;
for(int j=1;j<=k;++j)
while(A[j].remainder(g).compareTo(BigInteger.ZERO)==0)
A[j]=A[j].divide(g);
}
System.out.print("! "+t);
for(int i=1;i<=t;++i)
System.out.print(" "+B[i]);
System.out.println();
}
}