#Summer24003. 循环的映射

循环的映射

循环的映射

时间限制:5s5s

空间限制:256MB256MB

题目背景

首先,让我们定义两个集合。$Z_n =\{0,1,2,...,n-1\}, F=\{f|y=f(x), x∈Z_n,y∈Z_n\}$是从ZnZ_nZnZ_n的一一对映。不难得出 F 中有n!n! 个元素,元素 f 也可以理解成 0 到 n - 1 这 n 个数字所有的排列方案。

现在,我们在定义两个集合中元素的运算。定义 a+b(a,bZn)a + b(a,b ∈Z_n)是模 n 意义下的加法,fa+fb=fa(fb(x))(fa,fbF)f_a+f_b= f_a ( f_b (x))\quad (f_a, f_b∈F)也就是两个函数的复合。对于 n 个相同的f相加,我们可以写成f(n)=f+f+f++ff^{(n)}=f+f+f+…+f

可以发现,大部分的f是很没有意思的,相当于把n个数字随机打乱,因此我们现在要重点研究一种 f。定义F={ff(a)+f(b)=f(a+b)(a,bZn)}F^*=\{f|f(a)+f(b)=f(a+b)\quad(a,b ∈Z_n)\},也就是说这种经过这种f可以使得ZnZ_n中的元素运算规律保持不变。例如f(x)=x也就是保持不变就是一种符合条件的函数。

另外一方面,从函数嵌套的角度。A={xx=f(n)(nN)}A=\{x|x= f^{(n)}\quad (n \in N)\},这样可以生成一个有限集合,不妨记作A(f)A(f)。或者 A 和 B 都是元素为 f 的集合,那么可以有定义 C=AB={ff=fa+fb(faA,fbB)}C=A*B=\{f|f= f_a+f_b(f_a∈A,f_b∈B)\}。这些集合都是F的子集。

对于F,你既可以当成ZnZ_n的自我映射,也可以当成是对一些元素的排序,不难发现这很有研究价值。

题目描述

小陆最近对这样的集合与运算很感兴趣,他希望你帮忙研究一个问题。已知n,对于一个由ZnZ_n产生出的FF^*,对于每一个fFf∈F^*,都可以找到一个B ⊆F,使得FBA(f)F^*⊆ B*A(f)。现在,小陆需要你考虑当B的元素个数最小时,对于所有的fFf∈F^*,B的元素个数的总和。

(省流版:F=AutZn,fF,A={xx=f(n)}F^*=Aut\quad Z_n, f∈F^*, A=\{x|x=f^{(n)}\},求所有 ffF/A| F^*/A|之和)

输入格式

第一行一个正整数 T,表示测试样例数。

第二行 T 个正整数,每个数就是对应的 nn

输出格式

T 个正整数,就是所求的答案。

样例

输入:

3
1 3 114

输出:

1 3 210

样例解释

对于第一个样例,FF^*里只有x=f(x)x=f(x)A(f)A(f)也为{x=f(x)}\{x=f(x)\},那么可以找到B也为 {x=f(x)}\{x=f(x)\}AB=x=f(x)=FA*B={x=f(x)}= F^*

对于第二个样例,F={f1,f2}F^*=\{f_1,f_2\},其中f1f_1(00,11,22)(0\rightarrow 0, 1 \rightarrow 1, 2 \rightarrow 2), f2f_2(00,12,21)(0\rightarrow0, 1\rightarrow2,2\rightarrow1)A(f1)={f1},A(f2)={f1,f2}A(f_1)=\{f_1\}, A(f_2)=\{f_1, f_2\}。可以找到 B 分别为{f1,f2}\{f_1, f_2\}f1,{f1,f2}{f1}={f1,f2}=F{f_1}, \{f_1, f_2\}*\{ f_1\}=\{f_1, f_2\}= F^*,因此答案为 1+2=31+2=3

数据范围与约定

对于20%20\%的数据, T=1n10T=1,n\le10

对于40%40\%的数据, T=10n100T=10,n\le100

对于60%60\%的数据, T=100n10000T=100,n\le10000

对于100%100\%的数据, T=1000n30000T=1000,n\le30000