从“有多少个约数的个位是1”想到的～

mathe

根据上面表格，可以看出对于个位数是7的情况，（对应向量中第二个分量），

$d_7$最大的策略	可选模式	概率
如果约数数目k=2h	$7^1 11^{h-1}$	$1/2$
如果约数数目k奇数存在最小形如$4s+3$的奇数因子$k=(4s+3)h$	$7^{4s+3} 11^h$	$1/4+1/{4(4s+3)}$
不然	$7^{k-1}$	$1/4-1/{4k}$

同样对于个位是3的情况

$d_3$最大的策略	可选模式	概率
如果约数数目k=2h	$3^1 11^{h-1}$	$1/2$
如果约数数目k奇数存在最小形如$4s+3$的奇数因子$k=(4s+3)h$	$3^{4s+3} 11^h$	$1/4+1/{4(4s+3)}$
不然	$3^{k-1}$	$1/4-1/{4k}$

$d_9$最大的策略	可选模式	概率
如果约数数目k=2h	$19^1 11^{h-1}$	$1/2$
如果约数数目k为奇数	$19^{k-1}$	$1/2-1/{2k}$

$d_1$最小的策略	可选模式	概率
如果约数数目$k=2(4s+3)h$要求s最小	$7^{4s+2}19 11^{h-1}$	$1/4-1/{4(4s+3)}$
如果约数数目$k=(4s+3)(4t+3)(2h+1)$,要求$(4s+3)(4t+3)$最小	$7^{4s+2}17^{4t+2}11^{2h}$	$1/4-1/{4(4s+3)(4t+3)}$
如果约数数目$k=4h$	$3^{4h-1}$	$1/4$
如果约数数目$k=2(4h+1)$	$3^{8h+1}$	$1/4+1/{4(4h+1)}$
如果约数数目$k=4h+3$,而且k只有单个单次模3为4的素因子	$7^{4h+2}$	$1/4+1/{4(4h+3)}$
如果约数数目$k=4h+1$,而且k没有模3为4的素因子	$3^{4h}$	$1/4+3/{4(4h+1)}$

$d_1+d_7$最小的策略	可选模式	概率
如果约数数目$k=(4s+3)h$,要求$4s+3$最小	$3^{4s+2}11^{h-1}$	$1/2-1/{2(4s+3)}$
如果约数数目$k=2h$而且k没有形如$4s+3$的因子	$19^1 11^{h-1}$	$1/2$
如果约数数目$k=4h+1$而且k没有形如$4s+3$的因子	$3^{4h}$	$1/2+1/{2(4h+1)}$

$d_1+d_3$最小的策略	可选模式	概率
如果约数数目$k=(4s+3)h$,要求$4s+3$最小	$7^{4s+2}11^{h-1}$	$1/2-1/{2(4s+3)}$
如果约数数目$k=2h$而且k没有形如$4s+3$的因子	$19^1 11^{h-1}$	$1/2$
如果约数数目$k=4h+1$而且k没有形如$4s+3$的因子	$7^{4h}$	$1/2+1/{2(4h+1)}$

mathe

现在查看个位数是6的选择，根据前面，选择$k=rs$,那么有概率为
\(\begin{cases}
\frac1 4-\frac1{4r}&r=1 \pmod 4\\
\frac1 4-\frac{d_1}r&r=0 \pmod 4\\
\frac1 4+\frac1{4r}-\frac{d_7+d_1}r&r=3 \pmod 4\\
\frac1 4-\frac1{2r}+\frac{d_3}r&r=2 \pmod 4
\end{cases}\)
其中最后一种$d_3$达到$1/2$时概率可以取到$1/4$,而第三种在$d_1+d_7=1/4$时也可以取到概率$1/4$, 两者都要求$4|k$,可以优先考虑。
所以在$k$是4的倍数时，使用模式$2^1 3^1 11^{k/4-1}$即可达到这个最优概率$1/4$。
而k是2的倍数不是4的倍数时，有多种方案可以达到最大概率$1/4-1/{2k}$. 而k模4为1，那么选择第一种方案中$r=k$可以达到最优值$1/4-1/{4k}$。
而k模4为3，那么可以选择第三种方案中$r=k$可达到$1/4-3/{4k}$

mathe

20#中的计算表明所有集合$B(n)$中的元素必然可以写成$aW_1,bN\star W_1, cN^2\star W_1, dN^3\star W_1, eV_1, fN\star V_1, gH_1, h N\star H_1, i K_1$的线性组合，其中a,b,c,d,e,f,g,h,i是整数。当然如果系数0存在，那么它可以被归为任何一类
然后我们记$MaxP(n, V)$是$B(n)$中所有形如$aV$的元素中系数a的最大值，而$MinP(n,V)$是$B(n)$中所有形如$aV$的元素中系数a的最小值
而$M(n)={MaxP(n,V)| V \in B(n)} = {MinP(n,V)|V \in B(n)}$
我们可以发现$M(nm)$是$M(n)\star M(m)$的子集。
由于本题中，实际上我们只要对于每个k求出$M(k)$即可，所以就可以利用$M(nm)$是$M(n)\star M(m)$的子集这个性质计算所有的$M(n)$了
而计算$M(k)$

而所有计算的基础是19#中的基本模式，可以看出其中除了$19^{2x}$对应的模式中波动向量是$K_1+H_r$需要两项相加，而所有其它波动向量都只有一项
由于这些单项的向量之间的乘积还是一个单项向量，如果我们不使用模式$?9^{2x}$，那么得出的对应的波动向量必然是$aW_1,bN\star W_1, cN^2\star W_1, dN^3\star W_1, eV_1, fN\star V_1, gH_1, h N\star H_1, i K_1$中的一种。
而又因为$(K_1+H_a)\star (K_1+H_b)=K_1+H_{ab}$,由于所有这些模式运算可以任意交换顺序的，所以我们知道最终所有可能的模式必然是
$aW_1,bN\star W_1, cN^2\star W_1, dN^3\star W_1, eV_1, fN\star V_1, gH_1, h N\star H_1, i K_1$
或它们和某个$K_1+H_a$的复合。由于
$W_b\star(K_c+H_a)=K_{bc}+H_{ab}, N\star(K_c+H_a)=-K_c+N\star H_a, N^2\star(K_c+H_a)=K_c-H_a, N^3\star(K_c+H_a)=-K_c-N\star H_a$
$V_b\star(K_c+H_a)=V_{ab},H_b\star(K_c+H_a)=H_{ab},K_b\star(K_c+H_a)=K_{bc}$
所以我们得出最终所有波动向量形式是
$aW_1,bN\star W_1, cN^2\star W_1, dN^3\star W_1, eV_1, fN\star V_1, gH_1, h N\star H_1, i K_1$
$K_c+H_a, K_c-H_a,K_c+N\star H_a,K_c-N\star H_a$,其中$c|a$

而$(K_1+H_{2a+1})\star(K_1+H_{2b+1})=K_1+H_{(2a+1)(2b+1)}$说明模式$19^{2a}29^{2b}$和$19^{(2a+1)(2b+1)-1}$等效
   $(K_1+H_{2a+1})\star K_1=K_1$说明模式$19^{2a}29^{2b+1}$和模式$19$等效，也就是最优结果可以只使用一个9结尾的素因子。
而对于k的奇数因子，可以产生的基本模式在k模4为1时只有$W_k$,而在k模4为3时可以有$-N\star W_k, -N^3\star W_k$
由于$W_x\star W_y=W_{xy}$，所以它们之间混合只能再多产生一个$N^2\star W_k$,也就是如果不使用$19^x$这种模式，
那么能够产生的波动向量只有$W_k,N^2\star W_k, -N\star W_k, -N^3\star W_k$这四种，其中$W_k$在k模4为1时取到，$N^2\star W_k$在k模4为1而且存在模4为3的因子时取到，$-N\star W_k,-N^3\star W_k$在k模4为3时取到。

k	模式	波动向量
模4为1	$3^{k-1}$	$W_k$
模4为1含除3为1的因子uv=k	$3^{u-1}7^{v-1}$	$N^2\star W_k$
模4为3	$3^{k-1}$	$-N\star W_k$
模4为3	$7^{k-1}$	$-N^3\star W_k$

以及特殊奇数模式

k	模式	波动向量
奇数	$19^{k-1}$	$K_1+H_k$

对于各种求波动向量某分量最大最小或波动向量俩分量和求最大或最小时，选择模式时，参数k总是应该选择尽量大或尽量小，于是两种奇数模式组合在一起有
$(-N)^u \star (K_1+H_{r_2}), (-N)^u \star (K_{r_1}+H_r)$
而我们计算$K_1+H_{r_2}=[1/4+1/{2r_2}, -1/4, 1/4-1/{2r_2}, -1/4], K_{r_1}+H_r=[{r_2+2}/{4r}, -{r_2}/{4r}, {r_2-2}/{4r}, -{r_2}/{4r}]$
我们分别需要分析各个分量以及它们两两值得最值，所以都只要选$r_2$尽量小和$r_2$尽量大两种情况，而且其中$r_2=1$的退化情况还是可以有统一公式，转化为$H_1+K_1=W_1$,所以使用下面特殊模式我们只需要考虑$r_2$尽量大的情况，于是组合在一起有

奇数k	模式	波动向量
选择因子1	$11^{k-1}$	$W_1$
选择对大模4为1的因子h	$3^{h-1}$	$W_h$
选择两个最小除以4余数为3的因子u,v,(uv|k）	$3^{u-1}7^{v-1}$	$N^2\star W_{uv}$
选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）	$3^{u-1}7^{v-1}$	$N^2\star W_h$
选择最大模4为3的因子h	$3^{h-1}$	$-N\star W_h$
选择最大模4为3的因子h	$7^{h-1}$	$-N^3\star W_h$
选择最小模4为3的因子h	$3^{h-1}$	$-N\star W_h$
选择最小模4为3的因子h	$7^{h-1}$	$-N^3\star W_h$
选择因子1	$19^{k-1}$	$K_1+H_k$
选择对大模4为1的因子h,hs=k	$3^{h-1}19^{s-1}$	$K_h+H_k$
选择两个最小除以4余数为3的因子u,v,(uv|k）,k=uvs	$3^{u-1}7^{v-1}19^{s-1}$	$ K_{uv}-H_k$
选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）,k=uvs	$3^{u-1}7^{v-1}19^{s-1}$	$K_{uv}-H_k$
选择最大模4为3的因子h,k=hs	$3^{h-1}19^{s-1}$	$K_h-N\star H_k$
选择最大模4为3的因子h,k=hs	$7^{h-1}19^{s-1}$	$K_h+N\star H_k$
选择最小模4为3的因子h,k=hs	$3^{h-1}19^{s-1}$	$K_h-N\star H_k$
选择最小模4为3的因子h,k=hs	$7^{h-1}19^{s-1}$	$K_h+N\star H_k$

另外$V_{8k+2}=V_2\star W_{4k+1}, N\star V_{8k+2}=(N\star V_2)\star W_{4k+1}, V_{8k+6}=(N\star V_2) \star (-N\star W_{4k+3}), N\star V_{8k+6} = V_2 \star (-N^3\star W_{4k+3})$,我们得出每个$3^{4k+1},7^{4k+1}$可以用$3^1 13^{2k},3^1 7^{2k}, 7^1 3^{2k}, 7^1 17^{2k}$等模式替换,也就是说我们总可以找出最优方案
使得模式中如果出现3和7作为末位素的素因子而且次数是奇数的情况，那么必然是1次的。

而对约数总数k因子分解后,其中偶数因子的基本模式只有$3^{2k+1} => V_r,7^{2k+1} =>N\star V_r, 19^{2k+1}=>K_1, 3^{4k+3}=>0$这几种
而且由于$K_1 \star V_r=0$,所以这几种方案不会同时出现，而且最优方案总它们都可以转化为$3^1=>V_2, 7^1=>N\star V_2, 19^1=>K_1, 3^3=>0$这几种形式，对应仅使用因子2或4，所以说明我们寻找最优模式时，素因子2完全可以和其它奇数因子分离处理。
而考虑到实际上我们需要的总是系数最大或者最小的情况，所以所有中间的系数都可以抛弃。记$s=\lfloor {h+1}/2 \rfloor$
在表格中各种带参数的模式中，我们应该总是尽量选择这些参数k尽量大或尽量小
另外在$8|k$或$16|k$时分别有带同样系数的模式$V,NV,-V,-NV$或$H,NH,-H,-NH$全部同时出现，它们分别代表对应的V,H将它们四个坐标循环移动得到的结果，
由于各分量有负有正，绝对值都相等或为0，也就是最大值最小值必然都为对应非零值的绝对值和其相反数上取到（同样两个坐标相加的情况也符合），
而如果偶数部分选择了这些模式，和对应奇数部分相乘，最终结果也必然时这种模式（会把其它模式全部吸收掉，因为模式$WH=H,WV=V, (K+H)H=H, (K+H)V=V$)
由此我们要选择这个对应非零值绝对值最大的情况，对应参数k中挑选的2的幂最小的情况。但是在2的次数不超过2的部分，由于模式不全，就不能只选择部分，所以要全部考虑。
于是我们有

k的2的幂的部分	模式	波动向量
2|k	$19^1$	$K_1$
2|k	$3^1$	$V_2$
2|k	$7^1$	$N\star V_2$
4|k	$3^3$	$0$
4|k	$3^1 13^1$	$-N\star H_2$
4|k	$3^1 7^1$	$H_2$
4|k	$7^1 17^1$	$N\star H_2$
8|k	$3^1 13^1 23^1$	$-N\star V_4$
8|k	$7^1 17^1 37^1$	$-V_4$
8|k	$3^1 7^1 17^1$	$N\star V_4$
8|k	$3^1 7^1 13^1$	$V_4$
16|k	$3^1 13^1 23^1 43^1$	$-H_4$
16|k	$3^1 7^1 13^1 23^1$	$-N\star H_4$
16|k	$3^1 7^1 13^1 17^1$	$H_4$
16|k	$3^1 7^1 17^1 37^1$	$N\star H_4$

于是对于任意一个约数数目k,我们将其奇数因子部分和2的幂分别使用两个表格找出一些候选解，把两部分复合以后求其中最优解即可。而且如果选择了第二个标中k的2的幂不小于3次时，单独使用即可，不需要和第一部分组合，因为我们要求$H_x$或$V_x$中参数x尽量小
其中8|k情况下可以让每个$d_i-1/4$取到最小值$-1/8$和最大值$1/8$,$d_1+d_7-1/2$和$d_1+d_3-1/2$可以取到最小值$-1/4$
而16|k情况下可以让每个$d_i-1/4$取到最小值$-1/8$和最大值$1/8$,$d_1+d_7-1/2$和$d_1+d_3-1/2$可以取到最小值$-1/8$
所以8|k情况的解总是不差于16|k对应的解，可以不用考虑16|k情况。
由于两个表格候选数都可以超过10中，复合以后可以超过100种以上，人工分析比较困难，但是对于具体的k,让计算机求解已经非常容易

mathe

综合结果

k	模式	波动向量
选择因子1	$11^{k-1}$	$W_1$
选择对大模4为1的因子h	$3^{h-1}$	$W_h$
选择两个最小除以4余数为3的因子u,v,(uv|k）	$3^{u-1}7^{v-1}$	$N^2\star W_{uv}$
选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）	$3^{u-1}7^{v-1}$	$N^2\star W_h$
选择最大模4为3的因子h	$3^{h-1}$	$-N\star W_h$
选择最大模4为3的因子h	$7^{h-1}$	$-N^3\star W_h$
选择最小模4为3的因子h	$3^{h-1}$	$-N\star W_h$
选择最小模4为3的因子h	$7^{h-1}$	$-N^3\star W_h$
选择因子1,s为最大奇数因子	$19^{s-1}$	$K_1+H_s$
选择对大模4为1的因子h,hs为最大奇数因子	$3^{h-1}19^{s-1}$	$K_h+H_{hs}$
选择两个最小除以4余数为3的因子u,v,(uv|k）,uvs为最大奇数因子	$3^{u-1}7^{v-1}19^{s-1}$	$ K_{uv}-H_{uvs}$
选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）,uvs为最大奇数因子	$3^{u-1}7^{v-1}19^{s-1}$	$K_{uv}-H_{uvs}$
选择最大模4为3的因子h,hs为最大奇数因子	$3^{h-1}19^{s-1}$	$K_h-N\star H_{hs}$
选择最大模4为3的因子h,hs为最大奇数因子	$7^{h-1}19^{s-1}$	$K_h+N\star H_{hs}$
选择最小模4为3的因子h,hs为最大奇数因子	$3^{h-1}19^{s-1}$	$K_h-N\star H_{hs}$
选择最小模4为3的因子h,hs为最大奇数因子	$7^{h-1}19^{s-1}$	$K_h+N\star H_{hs}$
2|k	$19^1$	$K_1$
2|k,选择最大奇数因子h	$3^{h-1}19^1$	$K_h$
2|k	$3^1$	$V_2$
2|k	$7^1$	$N\star V_2$
2|k,选择对大模4为1的因子h	$3^{h-1}13^1$	$V_{2h}$
2|k,选择对大模4为1的因子h	$7^{h-1}3^1$	$N\star V_{2h}$
2|k, 选择两个最小除以4余数为3的因子u,v,(uv|k）	$3^{u-1}7^{v-1}13^1$	$-V_{2uv}$
2|k, 选择两个最小除以4余数为3的因子u,v,(uv|k）	$3^{u-1}7^{v-1}17^1$	$-N\star V_{2uv}$
2|k, 选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）	$3^{u-1}7^{v-1} 13^1$	$- V_{2h}$
2|k, 选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）	$3^{u-1}7^{v-1} 17^1$	$- N\star V_{2h}$
2|k, 选择最大模4为3的因子h	$3^{h-1}13^1$	$-N\star V_{2h}$
2|k, 选择最大模4为3的因子h	$3^{h-1}17^1$	$ V_{2h}$
2|k, 选择最大模4为3的因子h	$7^{h-1}3^1$	$N\star V_{2h}$
2|k, 选择最大模4为3的因子h	$7^{h-1}17^1$	$-V_{2h}$
2|k, 选择最小模4为3的因子h	$3^{h-1}13^1$	$-N\star V_{2h}$
2|k, 选择最小模4为3的因子h	$3^{h-1}17^1$	$V_{2h}$
2|k,选择最小模4为3的因子h	$7^{h-1}3^1$	$N\star V_{2h}$
2|k,选择最小模4为3的因子h	$7^{h-1}17^1$	$- V_{2h}$
4|k	$3^3$	$0$
4|k	$3^1 13^1$	$-N\star H_2$
4|k	$3^1 7^1$	$H_2$
4|k	$17^1 7^1$	$N\star H_2$
4|k, 选择对大模4为1的因子h	$3^{h-1}13^1 23^1$	$-N\star H_{2h}$
4|k, 选择对大模4为1的因子h	$3^{h-1}13^1 7^1$	$H_{2h}$
4|k, 选择对大模4为1的因子h	$3^{h-1}17^1 7^1$	$N\star H_{2h}$
4|k,选择两个最小除以4余数为3的因子u,v,(uv|k）	$3^{u-1}7^{v-1}13^1 17^1$	$-H_{2uv}$
4|k,选择最大模4为1含除3为1的因子h,而且h=uv,(u,v除以4余3）	$3^{u-1}7^{v-1}13^1 17^1$	$-H_{2h}$
4|k, 选择最大模4为3的因子h	$3^{h-1}13^1 17^1$	$-N\star H_{2h}$
4|k, 选择最大模4为3的因子h	$3^{h-1}13^1 23^1$	$-H_{2h}$
4|k, 选择最大模4为3的因子h	$3^{h-1}7^1 17^1$	$H_{2h}$
4|k, 选择最大模4为3的因子h	$7^{h-1}3^1 17^1$	$N\star H_{2h}$
4|k, 选择最小模4为3的因子h	$3^{h-1}13^1 7^1$	$-N\star H_{2h}$
4|k, 选择最小模4为3的因子h	$3^{h-1}7^1 7^1$	$ H_{2h}$
4|k, 选择最小模4为3的因子h	$7^{h-1}3^1 17^1$	$N\star H_{2h}$
4|k, 选择最小模4为3的因子h	$7^{h-1}17^1 37^1$	$- H_{2h}$
8|k	$3^1 13^1 23^1$	$-N\star V_4$
8|k	$7^1 17^1 37^1$	$-V_4$
8|k	$3^1 7^1 17^1$	$N\star V_4$
8|k	$3^1 7^1 13^1$	$V_4$

其中灰色部分又是可以淘汰的模式

mathe

记$F_k(x)=1+x+x^2+...+x^{k-1}$
对于奇数$n=p_1^{a_1}p_2^{a_2}...p_h^{a_h}$，其中$p_1,p_2,...,p_h$都不是2和5
那么
对于其中每个末位数为1的项$p_i^{a_i}$,我们将它替换为$F_{a_i+1}(1)$,
对于其中每个末位数为7的项$p_i^{a_i}$,我们将它替换为$F_{a_i+1}(x)$,
对于其中每个末位数为9的项$p_i^{a_i}$,我们将它替换为$F_{a_i+1}(x^2)$,
对于其中每个末位数为3的项$p_i^{a_i}$,我们将它替换为$F_{a_i+1}(x^3)$
这样我们就可以将n替换成函数$G_n(x)$
假设$G_n(x) -=c_1+c_7 x+c_9 x^2+c_3 x^3 (mod x^4-1)$
那么我们有结论，n的约数中，末位数为h的正好$c_h$个。

根据上面的结论，对于某个合数$m=u*v$,由于$F_m(x)=F_u(x)*F_v(x^u)$
所以$F_m(x)(mod x^4-1)=F_u(x) *F_v(x^{u (mod 4)})(mod x^4-1)$
这个结论说明，对于给定整数n,必然存在另外一个整数m,其因子分解中每个素因子次数都是素数减1，而m和n的所有约数中，末位数为1,3,7,9的数目都相等
也就是说，本题分析中，我们可以只考虑那些因子分解中每项次数都是素数减1的模式

而另外$G(1),G(-1),G(i),G(-i)$的取值可以完全确定$G(x)(mod x^4-1)$，而其中G(1)总是常数，G(i)和G(-i)总是共轭，所以只要分析G(-1)和G(i)的不同取值情况即可
而且容易看出
$G(1)=c_1+c_7+c_9+c_3$代表约数总数
$G(-1)=(c_1+c_9)-(c_7+c_3)$
$\Re{ G(i)} = c_1-c_9$
$\Im {G(i)} = c_7-c_3$

为方便起见，在记$f_{0,k}(x)=F_k(1),f_{1,k}(x)=F_k(x),f_{2,k}(x)=F_k(x^2),f_{3,k}(x)=F_k(x^3)$
给定一个约数数目$k=\prod_{i=1}^h p_i$,其中不同的$p_i$可以相同，也可以不同，我们需要找出$0<=d_1,d_2,...,d_h<=3$
计算出所有的$H_k^{(d_1,d_2,...,d_h)}(x)=\prod_{i=1}^h f_{d_i,p_i}(x)(mod x^4-1)$简记为$H_k(x)$,然后从中找出满足条件的最优解。
由于
\(f_{1,p_i}(-1)=\begin{cases} 0& p_i=2\\1&p_i>2 \end{cases}\)
\(f_{2,p_i}(-1)=p_i\)
\(f_{3,p_i}(-1)=\begin{cases} 0& p_i=2\\1&p_i>2 \end{cases}\)
\(f_{1,p_i}(i)=\begin{cases} 1+i& p_i=2\\1&p_i \equiv 1\pmod{4}\\i&p_i \equiv 3 \pmod{4} \end{cases}\)
\(f_{2,p_i}(i)=\begin{cases} 0& p_i=2\\1&p_i >2\end{cases}\)
\(f_{3,p_i}(i)=\begin{cases} 1-i& p_i=2\\1&p_i \equiv 1\pmod{4}\\-i&p_i \equiv 3 \pmod{4} \end{cases}\)
我们首先可以根据$H_k(-1)$和$H_k(i)$是否为0分成四类
第一类:
$H_k(-1)=H_k(i)=0$,这个要求k中，素因子2的次数至少为2，其中一个用于模式$7^1$或$3^1$,对应$f_{1,2}(-1)=0$或$f_{3,2}(-1)=0$,另外一个用于模式$19^1$,对应$f_{2,2}(i)=0$,这时我们知道必然有$H_k(1)=k,H_k(-1)=H_k(i)=H_k(-i)=0$,所以对应分布为$c_1=c_7=c_9=c_3=k/4$, 对应23#表格中波动向量为0的情况
第二类:
$H_k(i)=0, H_k(-1) != 0$, 这个要求使用了模式$19^1$,但是不能使用模式$7^1$或$3^1$,我们还需要计算这个分类中$H_k(-1)$的值
而且这时$c_1=c_9,c_3=c_7$
因为所有的$f_{2,2}(-1)=2=f_{0,2}(-1)$,也就是模式$9^1$使用多次和一次作用相同。而又因为\(f_{1,p_i}(-1)=f_{3,p_i}(-1)=1， p_i>2\),说明使用模式$7^{p_i-1}$和$3^{p_i-1}$也作用相同,都相当于在计算$H_k(-1)$时，将对应的奇数因子改为1， 而且$f_{2,p_i}(-1)=p_i=f_{0,p_i}(-1)$。所以$H_k(-1)$可以通过将$k$中部分奇数因子去除后得到。
也就是任意选择$d|k$,其中d为奇数，那么这时必然有第二类方案可以使得$H_k(-1)=k/d$,而这时$c_1=c_9=k(1/4+1/{4d}),c_7=c_3=k(1/4-1/{4d})$
不妨设$k=2^s r$其中$s>=1$,$r$是奇数，由于我们的目标是求$c_i$最大最小或其中两项之和最大或最小，这里相当于要求d最大和最小情况，分别对应$d=1$和$d=r$, 对应23#波动向量为$K_d$的情况
第三类:
$H_k(i) !=0, H_k(-1) = 0$，这个要求不使用模式$19^1$,但是可以使用若干次模式$7^1$或$3^1$。
于是对于k的每个因子2，可以选择对$H_k(i)$提供$1+i,1-i$的贡献或者保持2不变。而对于每个模4为1的素因子，可以保持不变也可以转化为1。而对于每个模4为3的素因子，可以不变，也可以转化为1，也可以选择转为$i$或$-i$。也就是$k$转为为$H_k(i)$时，可以挑选部分素因子进行转化，其中每个要转化素因子2在复平面上绝对值除以$sqrt(2)$,方向顺时针或逆时针转$pi/4$,每个模4为1的素因子只能转化为1；而模4为3的素因子绝对值转化为1，方向可以保持不变或顺时针转$pi/2$或逆时针转$pi/2$
所以如果我们选定k中需要转化的素因子，那么就确定了$H_k(i)$的绝对值，而如果转化的2的数目是偶数，$H_k(i)$的方向肯定是和某个坐标轴重叠的；而如果转化的2的数目是奇数，那么$H_k(i)$的方向是和坐标轴夹角$pi/4$。而两种情况都是最多有4个方向，其中在转化的2的数目不少于3个，或者转化的2的数目是1或2个但是同时至少转化一个模4为3的素数，那么就可以覆盖所有的4个方向。对于这两种可以覆盖所有方向的情况，我们知道最优结果应该是转化尽量多因子才可以得出最优结果。另外我们还要考虑转化的2的数目是1或2同时没有转化模4为3的素因子的情况。对应表格中一系列$2|k,4|k,8|k$等情况
第四类:
$H_k(i) !=0, H_k(-1) != 0$, 这时所有素因子2都不能转化，要保持不变。而部分奇数因子可以选择被转化，而这个转化对于$H_k(-1)$和$H_k(i)$是有限制的，$H_k(-1)$如果转化了，在$H_k(i)$中也一定转化掉，区别是在素数模4为3时，$H_k(i)$可以同时选择对结果的方向顺时针或逆时针旋转$pi/2$，也可以不旋转。所以结果总是有$|H_k(i)|$是 $H_k(-1)$的因子,而且两者都是从k中除去一个奇数因子，而$H_k(i)$方向可以在其它坐标轴方向。而在除去的奇数因子没有模4为3的素因子时，$H_k(i)$也只能选择正实数方向，但是在除去的奇数因子有一个模4为3的素因子时，就可以再同时选择两个虚轴方向了。而在除去的奇数因子有两个或以上模4为3的素因子时，就可以选择任意坐标轴方向了。

mathe

k 总约数， k=2^a*q	h=1(mod 4),  h|q, h最大		q=hs		q=rt	q=dj
	u,v=3(mod 4), u,v依次最小，可以相等		d=uv	vw=h	所以w=3(mod 4)	r=3(mod 4) r|q,r最大
	模式	波动向量	b1	b7	b9	b3	b1+b7	b1+b3
选择因子1	$11^{k−1}$	W1	3/4	-1/4	-1/4	-1/4	1/2	1/2
选择最大模4为1的因子h	$3^{h−1}$	Wh	3/(4h)	-1/(4h)	-1/(4h)	-1/(4h)	1/(2h)	1/(2h)
选择因子1,q=hs为最大奇数因子	$19^{q−1}$	K1+Hq	1/4+1/(2q)	-1/4	1/4-1/(2q)	-1/4	1/(2q)	1/(2q)
选择最大模4为1的因子h,q=hs为最大奇数因子	$3^{h−1}19^{s−1}$	Kh+Hq	1/(4h)+1/(2q)	-1/(4h)	1/(4h)-1/(2q)	-1/(4h)	1/(2q)	1/(2q)
选择最大模4为3的因子r	$3^{r−1}$	−N⋆Wr	1/(4r)	-3/(4r)	1/(4r)	1/(4r)	-1/(2r)	1/(2r)
选择最大模4为3的因子r	$7^{r−1}$	−N3⋆Wh	1/(4r)	1/(4r)	1/(4r)	-3/(4r)	1/(2r)	-1/(2r)
选择最小模4为3的因子u	$3^{u−1}$	−N⋆Wu	1/(4u)	-3/(4u)	1/(4u)	1/(4u)	-1/(2u)	1/(2u)
选择最小模4为3的因子u	$7^{u−1}$	−N3⋆Wu	1/(4u)	1/(4u)	1/(4u)	-3/(4u)	1/(2u)	-1/(2u)
选择最大模4为3的因子r,q=rt为最大奇数因子	$3^{r−1}19^{t−1}$	Kr−N⋆Hrt	1/(4r)	-1/(4r)-1/(2rt)	1/(4r)	-1/(4r)+1/(2q)	-1/(2rt)	1/(2rt)
选择最大模4为3的因子r,q=rt为最大奇数因子	$7^{r−1}19^{t−1}$	Kr+N⋆Hrt	1/(4r)	-1/(4r)+1/(2q)	1/(4r)	-1/(4r)-1/(2q)	1/(2q)	-1/(2q)
选择最小模4为3的因子u,q=uj为最大奇数因子	$3^{u−1}19^{j−1}$	Ku−N⋆Huj	1/(4u)	-1/(4u)-1/(2q)	1/(4u)	-1/(4u)+1/(2q)	-1/(2q)	1/(2q)
选择最小模4为3的因子u,q=uj为最大奇数因子	$7^{u−1}19^{j−1}$	Ku+N⋆Huj	1/(4u)	-1/(4u)+1/(2q)	1/(4u)	-1/(4u)-1/(2q)	1/(2q)	-1/(2q)
选择两个最小除以4余数为3的因子u,v,(uv|k）, d=uv	$3^{u−1}7^{v−1}$	N2⋆Wuv	-1/(4d)	-1/(4d)	3/(4d)	-1/(4d)	-1/(2d)	-1/(2d)
选择最大模4为1含除4为3的因子h,而且h=vw,(vw除以4余3）	$3^{w−1}7^{v−1}$	N2⋆Wh	-1/(4h)	-1/(4h)	3/(4h)	-1/(4h)	-1/(2h)	-1/(2h)
选择两个最小除以4余数为3的因子u,v,(uv|k）,d=uv,q=dj为最大奇数因子	$3^{u−1}7^{v−1}19^{j−1}$	Kd−Hq	1/(4d)-1/(2q)	-1/(4d)	1/(4d)+1/(2q)	-1/(4d)	-1/(2q)	-1/(2q)
选择最大模4为1含4余3的因子h,而且h=vw,(v,w除以4余3）,hs为最大奇数因子	$3^{w−1}7^{v−1}19^{s−1}$	Kh−Hq	1/(4h)-1/(2q)	-1/(4h)	1/(4h)+1/(2q)	-1/(4h)	-1/(2q)	-1/(2q)
2|k	$19^1$	K1	1/4	-1/4	1/4	-1/4	0	0
2|k,选择最大奇数因子q=hs	$3^{q−1}19^1$	Kq	1/(4q)	-1/(4q)	1/(4q)	-1/(4q)	0	0
2|k	$3^1$	V2	1/4	-1/4	-1/4	1/4	0	1/2
2|k	$7^1$	N⋆V2	1/4	1/4	-1/4	-1/4	1/2	0
2|k,选择对大模4为1的因子h	$3^{h−1}13^1$	V2h	1/(4h)	-1/(4h)	-1/(4h)	1/(4h)	0	1/(2h)
2|k,选择对大模4为1的因子h	$7^{h−1}3^1$	N⋆V2h	1/(4h)	1/(4h)	-1/(4h)	-1/(4h)	1/(2h)	0
2|k, 选择最小模4为3的因子u	$3^{u−1}13^1$	−N⋆V2u	-1/(4u)	-1/(4u)	1/(4u)	1/(4u)	-1/(2u)	0
2|k, 选择最小模4为3的因子u	$3^{u−1}17^1$	V2u	1/(4u)	-1/(4u)	-1/(4u)	1/(4u)	0	1/(2u)
2|k,选择最小模4为3的因子u	$7^{u−1}3^1$	N⋆V2u	1/(4u)	1/(4u)	-1/(4u)	-1/(4u)	1/(2u)	0
2|k,选择最小模4为3的因子u	$7^{u−1}17^1$	−V2u	-1/(4u)	1/(4u)	1/(4u)	-1/(4u)	0	-1/(2u)
2|k, 选择两个最小除以4余数为3的因子u,v,(uv|k）,d=uv	3u−17v−1131	−V2d	-1/(4d)	1/(4d)	1/(4d)	-1/(4d)	0	-1/(2d)
2|k, 选择两个最小除以4余数为3的因子u,v,(uv|k）,d=uv	3u−17v−1171	−N⋆V2d	-1/(4d)	-1/(4d)	1/(4d)	1/(4d)	-1/(2d)	0
2|k, 选择最大模4为1含除3为1的因子h,而且h=vw,(w,v除以4余3）	3w−17v−1131	−V2h	-1/(4h)	1/(4h)	1/(4h)	-1/(4h)	0	-1/(2h)
2|k, 选择最大模4为1含除3为1的因子h,而且h=vw,(w,v除以4余3）	3w−17v−1171	−N⋆V2h	-1/(4h)	-1/(4h)	1/(4h)	1/(4h)	-1/(2h)	0
4|k	$3^3$	0	0	0	0	0	0	0
4|k	$3^1  13^1$	−N⋆H2	0	-1/4	0	1/4	-1/4	1/4
4|k	3  7	H2	1/4	0	-1/4	0	1/4	1/4
4|k	$17^1  7^1$	N⋆H2	0	1/4	0	-1/4	1/4	-1/4
4|k, 选择对大模4为1的因子h	3h−1131231	−N⋆H2h	0	-1/(4h)	0	1/(4h)	-1/(4h)	1/(4h)
4|k, 选择对大模4为1的因子h	3h−113171	H2h	1/(4h)	0	-1/(4h)	0	1/(4h)	1/(4h)
4|k, 选择对大模4为1的因子h	3h−117171	N⋆H2h	0	1/(4h)	0	-1/(4h)	1/(4h)	-1/(4h)
4|k,选择两个最小除以4余数为3的因子u,v,(uv|k）d=uv	$3^{u−1}7^{v−1}13^1 17^1$	−H2d	-1/(4d)	0	1/(4d)	0	-1/(4d)	-1/(4d)
4|k,选择最大模4为1含除3为1的因子h,而且h=vw,(v,w除以4余3）	3w−17v−1131171	−H2h	-1/(4h)	0	1/(4h)	0	-1/(4h)	-1/(4h)
8|k	$3^1 13^1 23^1$	−N⋆V4	-1/8	-1/8	1/8	1/8	-1/4	0
8|k	7  17 37	−V4	-1/8	1/8	1/8	-1/8	0	-1/4
8|k	3  717	N⋆V4	1/8	1/8	-1/8	-1/8	1/4	0
8|k	3  7 13	V4	1/8	-1/8	-1/8	1/8	0	1/4

由此可以判断我们计算过程中需要判断k是否含有0个,1个,2个或以上模4为3的素因子，以及素因子2的次数是0，1，2，$>=3$来分成最多9类。表格中灰色部分是淘汰的部分，不需要考虑

mathe

	模式	波动向量	b1	b7	b9	b3	b1+b7	b1+b3
选择因子1	$11^{k−1}$	W1	3/4	-1/4	-1/4	-1/4	1/2	1/2
选择因子1,q=hs为最大奇数因子	$19^{q−1}$	K1+Hq			1/4-1/(2q)
选择最大模4为1的因子h,q=hs为最大奇数因子	$3^{h−1}19^{s−1}$	Kh+Hq	1/(4h)+1/(2q)	-1/(4h)		-1/(4h)	1/(2q)	1/(2q)
选择最大模4为3的因子r	$3^{r−1}$	−N⋆Wr	1/(4r)
选择最小模4为3的因子u	$3^{u−1}$	−N⋆Wu				1/(4u)	-1/(2u)
选择最小模4为3的因子u	$7^{u−1}$	−N3⋆Wu		1/(4u)				-1/(2u)
选择两个最小除以4余数为3的因子u,v,(uv|k）, d=uv	$3^{u−1}7^{v−1}$	N2⋆Wuv	-1/(4d)
2|k	$19^1$	K1			1/4		0	0
2|k,选择最大奇数因子q=hs	$3^{q−1}19^1$	Kq	1/(4q)
2|k	$3^1$	V2				1/4
2|k	$7^1$	N⋆V2	1	1/4
2|k,选择最小模4为3的因子u	$7^{u−1}17^1$	−V2u	-1/(4u)
4|k	$3^3$	0	0
4|k	$3^1  13^1$	−N⋆H2					-1/4
4|k	$17^1  7^1$	N⋆H2						-1/4
8|k	$3^1 13^1 23^1$	−N⋆V4	-1/8

mathe

现在容易分析各种末位数什么时候取到最大概率了。
末位数是1

条件	模式	波动分量	概率
任意	$11^{k-1}$	$3/4$	$1$

末位数是7

条件	模式	波动分量	概率
$2|k$	$7^1 11^{k/2-1}$	$1/4$	$1/2$
k奇数，存在最小$u -=3(mod 4), u|k$	$7^{u-1} 11^{k/u-1}$	$1/{4u}$	$1/4+1/{4u}$
k奇数,不存在$u -=3(mod 4),u|k$	$3^{k-1}$	$-1/{4k}$	$1/4-1/{4k}$

末位数是9

条件	模式	波动分量	概率
$2|k$	$19^1 11^{k/2-1}$	$1/4$	$1/2$
k奇数	$19^{k-1} $	$1/4-1/{2k}$	$1/2-1/{2k}$

末位数是3

条件	模式	波动分量	概率
$2|k$	$3^1 11^{k/2-1}$	$1/4$	$1/2$
k奇数，存在最小$u -=3(mod 4), u|k$	$3^{u-1} 11^{k/u-1}$	$1/{4u}$	$1/4+1/{4u}$
k奇数,不存在$u -=3(mod 4),u|k$	$3^{k-1}$	$-1/{4k}$	$1/4-1/{4k}$

末位数是5

条件	模式	概率
任意	$5^{k-1}$	${k-1}/k$

末位数是0

条件	模式	概率
取$k=uv$,使得$|u-v|$最小	$2^{u-1}5^{v-1}$	${(u-1)(v-1)}/k$

末位数是2 (后面需要结合11#公式)

条件	模式	概率
$2|k$, 取11#中$r -=2 (mod 4)，d_1=1$	$2^1 11^{k/2-1}$	$1/2$
k奇数，存在最小$u -=3(mod 4), u|k$取11#中$r -=3 (mod 4),r=u,d_7+d_9=0$	$2^{u-1} 11^{k/u-1}$	$1/4+1/{4u}$
k奇数,不存在$u -=3(mod 4),u|k$,取11#中$r -= 1(mod 4), r=k$	$3^{k-1}$	$1/4-1/{4k}$

末位数是4,前面表格说明了$d_7<=1/2,d_9<=1/2,d_3<=1/2$

条件	模式	概率
存在最小$u -=3(mod 4), u|k$取11#中$r -=3 (mod 4),r=u,d_3+d_9=0$	$2^{u-1} 11^{k/u-1}$	$1/4+1/{4u}$
不存在$u -=3(mod 4), u|k$，但是$4|k$,取11#中$r -=0(mod 4)$	$2^3 11^{k/4-1}$	$1/4$
k不是4的倍数，不存在$u -=3(mod 4), u|k$，k的最大奇数因子为r，可以取11#中$r -=1(mod 4)$	$2^{r-1} 11^{k/r-1}$	$1/4-1/{4r}$

末位数是8,参考17#

条件	模式	概率
$4|k$	$2^{k-1} $	$1/4$
\(4\nmid k\),k最大奇数因子r有$r -=1(mod 4)$	$2^{r-1} 11^{k/r-1}$	$1/4-1/{4r}$
\(4\nmid k\),k最大奇数因子r有$r -=3(mod 4), k=2r$	$2^{r-1} 19^1$	$1/4-1/{2k}$
\(2\nmid k\),$k -=3(mod 4)$	$2^{k-1}$	$1/4-3/{4k}$

末位数是6,参考22#

条件	模式	概率
$4|k$	$2^1 3^1 11^{k/4-1} $	$1/4$
\(k\equiv 1\pmod{4}\)	$2^{k-1}$	$1/4-1/{4k}$
\(k\equiv 2\pmod{4}\)	$2^{k-1}$	$1/4-1/{2k}$
\(k\equiv 3\pmod{4}\)	$2^{k-1}$	$1/4-3/{4k}$