设n>3是素数,证明:小于n的正整数中除1和n-1外可分成对,使得每一对中的两个数互为模n逆.

问题描述:设p是奇素数,1≤x≤p-1,如果存在一个整数y(1≤y≤p-1),使得x=y²(modp),则称y是x的模p平方根.例如,63是55的模103平方根.试设计一个求整数x的模p平方根的拉斯维加斯算法.算法的计算时间应为logp的多项式.

算法设计:设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数p和x.

结果输出:将计算的x的模p平方根输出到文件output.txt.当不存在x的模p平方根时,输出0.

A.A+A^T是对称矩阵

B.AA^T和A^TA都是对称矩阵

C.若A是对称矩阵，则A^k(k为正整数)为对称矩阵

D.若A是反称矩阵，则A^k(k是正整数)为反称矩阵

算法设计:对于给定的实直线上的n个点和闭区向的长度k,计算覆盖点集的最少区间数.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k,表示有n个点,且固定长度闭区间的长度为k.接下来的1行中有n个整数,在示n个点在实直线上的坐标(可能相同).

结果输出;将计算的最少区间数输出到文件output,txt.

考虑下面的无限循环算法:

每个素数都会被上述算法输出.但是除了所有素数,算法可能偶尔错误地输出某些合数.说明上述情况不太可能发生.或更精确,证明上述算法错误地输出一个合数的概率小于1%.