Jacobi记号

对每组由a和n两个数字字符（中间以一个空格隔开）组成的输入数据，输出对应的Jacobi记号$J(a,n)$的值。

a和n都是非负整数且n为奇数。Jacobi记号的递归定义如下：

$J(a,1)=1$。

若n为素数，则$J(a,n)=\begin{cases}0 & 若a=0 \pmod n \\ 1 & 若a模n是完全平方数 \\ -1 & 其它情况 \end{cases}$

若$n=xy$且$x,y>1$，则$J(a,n)=J(a, x)J(a, y)$。

注意由于涉及到n的质因数分解，因此直接用定义计算是非常低效的。

本题难度:

解答

定义函数$f(a,b)$来递归计算$J(a,b)$的值。

若$a=0$，则根据定义只有在$b=1$时返回$1$,否则返回$0$。

否则若$a$是奇数，则用该页面的公式（6），即Jacobi记号的二次互反律作递归。

否则若$a$是偶数，则用定义中的第三条积性结合该页面的公式（13）作递归。

最终代码有三行。

代码长度：172字节 vs. 全站第一：116字节。

import sys
f=lambda a,b:[-1,1][a%4==1or b%4==1]*f(b%a,a)if a%2else[-1,1][b%8in(1,7)]*f(a//2,b)if a else(b==1)*1
for z in sys.argv[1:]:p,q=map(int,z.split());print(f(p%q,q))