抱歉这次题目的区分度设置的不是很好。02由于测试的时候没带log，而比赛时评测机压力较大，所以不小心卡到了log的非常抱歉。04数据有点弱给大家带来了困惑不好意思，由于有点卡常数，所以将时限放宽到8s/16s。非常感谢大家的支持！
## 1001. zxa and set
通过观察样例猜测答案即$\max(a_i)$，可以对小规模的数据进行模拟验证，实际答案就是$\max(a_i)$，时间复杂度$O(n)$。
由于$a_i$互不相同，因此可以考虑每个元素在哪些子集中是最小值。
设$a_i$是$A$中第$k$大的元素，以$a_i$为最小值的集合只能包含不小于$a_i$的元素，因此这样的集合有$2^{k-1}$个。
如果$k=1$，则只有$\{a_i\}$以$a_i$为最小值；否则，上述集合中包含最大元素的子集和不包含最大元素的子集的元素个数奇偶性不同，对答案的贡献相互抵消。因此有$S_{odd}-S_{even}=\max(a_i)$。
实际上，$a_i$不需要互不相同，也可以得到答案是$\max(a_i)$的结论。
## 1002. zxa and wifi
通过二分在$O(n\log n)$的时间复杂度下将路由器能覆盖的区间$[l_i,r_i]$求出来，并令$f[i][j]$表示用$i$个路由器覆盖前$j$个点的最小代价。
对于第一种方案，选取$j$点设置路由器可以得到的转移是$f[i][r_j]\leftarrow\min_{l_j-1\leq k\leq r_j}{f[i-1][k]} + a_i$。
对于第二种方案，选取$j$点设置光缆可以得到的转移是$f[i][j]\leftarrow f[i][j-1]+b_i$。
因此可以利用树状数组维护后缀区间最大值做到离线$O(nk\log n)$。
注意到选择互相包含的区间是不会成为最优解的，因此可以将第一组转移改为$f[i][r_j]\leftarrow\min_{l_j-1\leq k}{f[i-1][k]} + a_i$，即可做到$O(nk)$。
## 1003. zxa and leaf
二分答案$L$，检查是否存在答案不超过$L$的解，也即对于任意一条边上的两个点$u$和$v$，有$|level_u-level_v|\leq L$，如果能维护出每个点可能的取值区间就可以判断是否有解了。
对于$n>1$的情况，随便找点做根，做树形dp即可，总的时间复杂度为$O(n\log\max(w))$。
觉得dfs容易爆栈的话可以设一个虚点做起点，连向已经确定$level$的叶子，通过bfs确定一个拓扑序，在序上更新即可，时间复杂度同上。
Claris说随便选个点bfs就可以了。
这个题可以扩展，确定$level$的点可以不是叶子，扩展版本用虚树做也是十分容易的。
## 1004 zxa and xor
由于异或运算的特性，答案可以按位考虑，只需要维护出当前状态有多少对$(a_i+a_j)$的第$k$位是$1$，做$O(\log\max(a_i))$次即可。
$(a_i+a_j)$的第$k$位是$1$，即$((a_i+a_j)\;mod\;2^{k+1})\geq2^k$，而$0\leq(a_i\;mod\;2^{k+1})+(a_j\;mod\;2^{k+1}) < 2^{k+2}$，所以若令$b_i=(a_i\;mod\;2^{k+1})$，则对于给定的$i$，满足条件的$j$有$2^k-b_i\leq b_j<2^{k+1}-b_i$或者$b_j\geq 2^{k+1} + 2^k - b_i$。
利用离散型权值线段树可以很简便地维护题目中的修改和查询，总时间复杂度$O(n\log n\log\max(a_i))$。
## 1005 zxa and lcm
题目名为LCM，但实际需要一些最大公约数(Greatest Common Divisor)的知识。
由生成的公式可以看出$f_n=1+x+x^2+\cdots+x^{n-1}=\frac{1-x^n}{1-x}(n>1)$，而$(1-x^p)|(1-x^q)$当且仅当$p|q$，同理$f_p|f_q$当且仅当$p|q$，由此可以归纳法或反证法或观察欧几里得算法得到结论：$gcd(f_a,f_b)=f_{gcd(a,b)}$。
而对于任意两个数都有$a\cdot b=gcd(a,b)\cdot lcm(a,b)$，故有$lcm(f_a,f_b)=\frac{f_a\cdot f_b}{f_{gcd(a,b)}}$。
考虑每个质因子的幂次，不难得到$gcd(lcm(a_1,a_2,\cdots),b)=lcm(gcd(a_1,b),gcd(a_2,b),\cdots)$，故有$gcd(lcm(f_a,\cdots),f_b)=lcm(gcd(f_a,f_b),\cdots)$。
因此可以推出$lcm(f_a,f_b,f_c)=\frac{lcm(f_a,f_b)\cdot f_c}{gcd(lcm(f_a,f_b), f_c)}=\frac{f_a\cdot f_b\cdot f_c}{gcd(f_a,f_b)\cdot lcm(gcd(f_a, f_c), gcd(f_b, f_c))}=\frac{f_a\cdot f_b\cdot f_c\cdot f_{gcd(a,b,c)}}{f_{gcd(a,b)}\cdot f_{gcd(a,c)}\cdot f_{gcd(b,c)}}$。
通过观察或者归纳法，不难得到$lcm(f_{a_1},f_{a_2},\cdots,f_{a_n})=\prod_{k=1}^{n}\prod_{x_1 < x_2 < \cdots < x_k}{(-1)^{k+1}\cdot f_{gcd(a_{x_1},a_{x_2},\cdots,a_{x_k})}}$。其实上面的这些推导只需要不断地集合最小值反演最大值即可。
设$[x]$为布尔表达式$x$的值，如果$x$为真，则$[x]=1$，否则$[x]=0$。如果令$g_n$满足$f_n=\prod_{d|n}{g_d}$，则有$f_{gcd(a,b)}=\prod_{d|gcd(i,j)}{g_d}=\prod_{d}{[d|i][d|j]g_d}$，更一般地有$f_{gcd(a_{x_1},a_{x_2},\cdots,a_{x_k})}=\prod_{d}{[d|a_{x_1}][d|a_{x_2}]\cdots[d|a_{x_k}]g_d}$。
$\prod_{k=1}^{n}\prod_{x_1 < x_2 < \cdots < x_k}{(-1)^{k+1}\cdot f_{gcd(a_{x_1},a_{x_2},\cdots,a_{x_k})}}$
$=\prod_{k=1}^{n}\prod_{x_1 < x_2 < \cdots < x_k}\prod_{d}{(-1)^{k+1}[d|a_{x_1}][d|a_{x_2}]\cdots[d|a_{x_k}]g_d}$
$=\prod_{d}{g_d\prod_{k=1}^{n}\prod_{x_1 < x_2 < \cdots < x_k}{(-1)^{k+1}[d|a_{x_1}][d|a_{x_2}]\cdots[d|a_{x_k}]}}$
$=\prod_{d}{g_d\cdot h(d)}$
其中$h(d)$即是否存在一个$a_i(1\leq i\leq n)$使得$d|a_i$，上述表达式即容斥的过程，但由于$\max(a_i)=m$，因此可以$O(m\log m)$计算出$h(d)$。而$g_n=\frac{f_n}{\prod_{d < n,d|n}{g_d}}$，也可以$O(m\log m)$计算。
按照上面的方法做就可以通过了，也可以表示成$g_n=\prod_{d|n}{\mu(d)f_d}$，然后再化简式子，计算$f_n$在答案中的幂次$c_n=h(n)-\sum_{n < d,n|d}{c_d}$，将答案表示成$\prod_{d=1}^{m}{h(d)f_d^{c_d}}$，可以减小常数，注意$c_d$可能是负数。
其实$x$可以为任意正整数，为了降低题目难度所以有$1 < x < p$，便于大家思考到正解。
##1001.Solution
考虑题目的原型，即给定$z$，寻找是否存在一组$(x,y)$，满足$x^{2}-y^{2}=z$
我们可以构造两组等式$\begin{bmatrix}
(k+1)^{2}-k^{2}=2k+1
\\
(k+1)^{2}-(k-1)^{2}=4k
\end{bmatrix}$，
很容易得出结论，当z为奇数或者4的倍数时，方程一定有正整数解
其实本来可以高精度的但是。。[捂脸熊省流量版.jpg]
##1002.Solution
直接暴力显然TLE，考虑按位DFS
每一位只可能是4或7
所以根据这个来DFS即可，时间复杂度$O(T*2^{log_{10}n})$
考虑到T特别大，不可能每次都DFS
而经过计算，$2^{18}=262144$，所以全部储存下来
对于每次询问，二分即可
考虑一个边界条件，即当结果爆ll怎么办？
即答案应当为10个4、10个7的时候，显然unsigned long long也不行
那么只能采用特判了
##1003.Solution
首先，对于每一个串i跑一次manancher，令$g[i][j]=p[j]-1$
这样，g就存储了所有的回文子串的长度
为了方便，把g降到一维表示
不妨把每一个子串抽象成一个物品
费用为二维的，即{长度，1}
价值是Bool型的
这样就成了一个二维判断可行性费用背包问题
设$f(i,j)$表示当前选出的长度为i，已经选了j个串，这个状态能否达到
$f(i,j)=f(i,j)|f(i-g(k),j-1)$
这样，时间复杂度为$O(L*K*N^{2})$
显然还是过不去
我们分析，发现其实g是会大量重复的
那么不妨当做多重背包来处理
时间复杂度降为$O(L*K*N*log\sum Li)$
##1004.Solution
这道题就是在一个子树上询问第k大，于是我们用dfs序将树上询问第k大转化为区间询问第k大，套用主席树即可，另外树套树常数较大，可能过不了
最后的提醒，这道题如果使用区间第k大的话一定要预处理n个答案后，m个询问$O(1)$查询才能AC
##1005.Solution
这个题按照题目说所的步骤计算出结果是很难的。
先移除所有被删除的格子。
然后，我们找出可访问的格子改变的数目（在增加新的步数的基础上）。
首先，改变（的数目）显得不稳定，但是，在某些点，我们看出图形（的轮廓）不会再被改变，
只会扩张，很明显这个图形是二维的，因此，增长的“面积”是一个二次方函数。
事实上，一个简单的检验可以得知，每一轮所增加的格子，是上一轮所增加的格子+28.，
要求某一点，你可以简单的使用等差数列求和。
这个结果和删除格子是相似的。总之，有许多种可能性。
任何被占或者将被占的格子，第一种情况，bfs已经足够找到解。
在第二种，用同样的方法：超时。
当图形“变得稳定”的时候，新增加的格子满足相同的规则“上一轮增加的+28”，
总之，由于限制被删除的格子（-10 <= x , y <= 10）被处理的相当的快，
所以我们先用bfs找到不变的图形，然后再用等差数列求和。
##Machine
红、绿、蓝分别表示0、1、2，每次操作就相当于+1，原问题就转化为求$n$的三进制
表示的最低的$m$位，即求 $n$ mod $3^m$的三进制表示。
复杂度 $O(m)$
##Matrix
对于交换行、交换列的操作，分别记录当前状态下每一行、每一列是原始数组的哪一行、哪一列即可。
对每一行、每一列加一个数的操作，也可以两个数组分别记录。注意当交换行、列的同时，也要交换增量数组。
输出时通过索引找到原矩阵中的值，再加上行、列的增量。
复杂度$O(q+mn)$
##String
有一个明显的性质：如果子串$(i,j)$包含了至少$k$个不同的字符，那么子串$(i,k),(j < k < length)$也包含了至少$k$个不同字符。
因此对于每一个左边界，只要找到最小的满足条件的右边界，就能在$O(1)$时间内统计完所有以这个左边界开始的符合条件的子串。
寻找这个右边界，是经典的追赶法（尺取法,双指针法）问题。维护两个指针（数组下标），轮流更新左右边界，同时累加答案即可。复杂度 $O(length(S))$。
##Robot
记路径长度为$n$,那么机器人最多向右走$\lfloor \frac{n}{2} \rfloor$步并向左走$\lfloor \frac{n}{2} \rfloor$步。
$Ans(n) = \sum_{i=0}^{\lfloor \frac{n}{2} \rfloor} C_n^{2i} \ Catalan(i)$
其中$Catalan(n)$表示第$n$个卡特兰数。
卡特兰数定义：$Catalan(n)=\frac{C_{2n}^n}{n+1}$
递推公式$Catalan(n)=\frac{4n-2}{n+1}\ Catalan(n-1)$
基于$n$的取值范围，此题可以预处理出$1,000,001$以内的乘法逆元、卡特兰数。
每次询问，都可以递推组合数，或者提前一次性预处理好阶乘和阶乘的逆元得到组合数；累加组合数与相应卡特兰数的乘积，得到答案。
事实上，$Ans(n)$是第$n$个默慈金数，还有更高效的递推公式：
$M_{n+1}=M_n+ \sum_{i=0}^{n-1}M_i M{n-1-i} = \frac{(2n+3)M_n+3nM_{n-1}}{n+3}$。
##Function
记$f(n)=(a+\sqrt{b})^n+(a-\sqrt{b})^n $。显然$f(0)=(a+\sqrt{b})^0+(a-\sqrt{b})^0=1+1=2$。$f(1)=(a+\sqrt{b})+(a-\sqrt{b})=2a$。
当$n\geq2$时 $f(n)=2af(n-1)+(b-a^2)f(n-2)$等式两边分别展开，很容易验证这个等式的正确性。推导时，将$2a$写作$(a+\sqrt{b})+(a-\sqrt{b})$,
用它和$f(n-1)$相乘，再减掉多余的部分，稍作整理就能得到以上等式。由于$2a$和$b-a^2$都是常数，这是线性递推方程，很容易得到$O(n)$（朴素递推）
和$O(\log n)$(矩阵快速幂）的方法求解。但是，如果直接用矩阵快速幂求解，复杂度是$O(\log{x^y})$即$O(y\log x)$的，不能通过本题，还需要更深入
的分析问题。
分别就$b$是否为$1,000,000,007$的平方剩余分类讨论（下文中 P 表示 1,000,000,007）：
如果$b$是$P$的平方剩余，设$t^2 \equiv b$。那么$f(n) \equiv (a+t)^n+(a-t)^n \equiv (a+t)^{n\ mod\ (P-1)}+(a-t)^{n\ mod\ (P-1)}$
$f(n)$是周期为$P-1$的函数。
如果$b$不是$P$的平方剩余，下面证明$f(n)$的周期为$P^2-1$。
将$f(P^2)$用二项式定理展开，注意到所有的$\sqrt b$的奇次项都正负抵消，所以$f(n)$只包含$\sqrt b$的偶次项。由Lucas 定理可知，$C_{P^2}^i(1\leq i\leq P^2)$
的非零取值只有$C_{P^2}^0 =C_{P^2}^{P^2}=1$，所以$f(P^2)=2a^{P^2} = 2a^{(P+1)(P-1)+1} \equiv 2a = f(1)$。
由Lucas定理 $C_{P^2+1}^i(1\leq i\leq P^2+1)$的非零取值有
$C_{P^2+1}^0,C_{P^2+1}^1,C_{P^2+1}^{P^2},C_{P^2+1}^{P^2+1}$。
$f(P^2+1)=2(a^{P^2+1}+{(\sqrt b)}^{P^2 +1})=2(a^{(P+1)(P-1)+2}+b{(\sqrt b)}^{P^2-1})\equiv 2(a^2+b(b^{\frac{P-1}{2}})^{P+1})=$
$2(a^2+b(-1)^{P+1})=2(a^2+b)=f(2)$
因为$f(P^2) \equiv f(1)$，$f(P^2+1)\equiv f(2)$，并且由线性递推方程可以，每一项都只与前两项有关，所以$f(n) \equiv f(n+(P^2-1)),(n>=1)$
接下来证明$f(0) \equiv f((P^2-1))$。
如果$a^2=b$,那么$f(n)=(a+\sqrt b)^n+(a- \sqrt b)^n=(2a)^n \equiv (2a)^{n\ mod\ (P-1)}$
所以$f(P^2-1) \equiv f((P^2-1)\ mod\ (P-1)) \equiv f(0)$；
如果$a^2 \neq b$，那么$f(2)=2af(1)+(b-a^2)f(0)$，并且$f(P^2+1)=2af(P^2)+(b-a^2)f(P^2-1)$。
已证$f(1)\equiv f(P^2)$，和$f(2) \equiv f(P^2+1)$,以上两式相减得：
$(b-a^2)(f(P^2-1)-f(0)) \equiv 0$,而$(b-a^2)\nmid P$，所以$f(P^2-1)-f(0) \equiv 0$，即$f(0)\equiv f(P^2-1)$。
至此证毕如果$b$不是$P$的平方剩余，那么$f(n)$的周期为$P^2-1$
这样，只需判断$b$是否是$P$的平方剩余，然后视情况,将$x^y$对周期取模，然后再用矩阵快速幂即可求解此问题。实际上，由于$P-1$是$P^2-1$的因子，所以周期为$P-1$的函数，$P^2-1$
也是它的周期。从代码简捷和逻辑简单的角度考虑，可以直接求$f(x^y\ mod \ (P^2-1))\ mod\ P$。
##1001
因为每个数可以用很多次,所以只要这个集合中有1,那么就可以加出所有的数来.
注意最后要判定一下是否有0.
之前版本的题目描述是用的自然数,后来因为有歧义换成了非负整数.
(本来是打算留个自然数当Trick的..sad story..)
#1002
考虑一条以$(0,0)$为起点,$(x,y)$为终点的线段上格点的个数（不包含端点时）,一定是$gcd(x,y)-1$,这个很显然吧.
然后整个网格图范围内的格点数目是$\frac {q*(q-1)} 2$.
所以答案就是$\frac {q*(q-1)} 2 -$ 所有线段上的格点的个数.
因为$gcd(a,b)=gcd(a,b-a)\ (b>a)$,所以$gcd(x,y)=gcd(x,p-x)=gcd(x,p)$,p是质数,所以$gcd(x,y)=1$,所以线段上都没有格点,所以答案就是$\frac {q*(q-1)} 2$.
#1003
观察递推式我们可以发现，所有的$f_i$都是$a$的幂次，所以我们可以对$f_i$取一个以$a$为底的$log$，即$g_i=log_a\ f_i$
那么递推式变成$g_i=b+c*g_{i-1}+g_{i-2}$,这个式子可以矩阵乘法
这题有一个小trick，注意$a\ mod\ p=0$的情况.
##1004
考虑对给定的出圈序列进行一次模拟,对于出圈的人我们显然可以由位置,编号等关系得到一个同余方程
一圈做下来我们就得到了n个同余方程
对每个方程用扩展欧几里得求解,最后找到最小可行解就是答案.
当然不要忘了判无解的情况.
有非常多选手似乎都是一眼标算然后写挂了,对此表示很遗憾,但是此题确实是比较容易写挂的...
#1005
首先考虑暴力,显然可以直接每次$O(n^2)$的连边,最后跑一次分层图最短路就行了.
然后我们考虑优化一下这个连边的过程 ,因为都是区间上的操作,所以能够很明显的想到利用线段树来维护整个图,连边时候找到对应区间,把线段树的节点之间连边.这样可以大大缩减边的规模,然后再跑分层图最短路就可以了.
但是这样建图,每一次加边都要在O(logn)个线段树节点上加边,虽然跑的非常快,但是复杂度仍然是不科学的.
为了解决边的规模的问题,开两棵线段树,连边时候可以新建一个中间节点,在对应区间的节点和中间节点之间连边
进一步缩减了边的规模,强行下降一个数量级
最后跑一下分层图最短路就行了
复杂度$O(mlog^2n)$
什么你会线段树但是不会分层图最短路?安利JLOI2011飞行路线.
因为边的数目还是相对比较多的,所以不能使用SPFA,而要使用Heap-Dijkstra来做最短路,但是不排除某些厉害的选手有特殊的SPFA姿势可以做或者普通
SPFA写的比较优美就不小心跑过去了...
##1001
不妨令$n\leq m$。
如果$n>6$，由于所有角都大于120度且小于180度，也就是说，两个角一定不够，而三个角一定过多。因此一定无解；
当$n\leq6$时，如果$n=3$或$n=4$或$n=6$，那么显然只需要正$n$边形的角就可以了。如果$n=5$，则已经有一个108度的角。若这种角：不取，则显然仅当$m=6$时有解；取1个，则还差$360-108=252$（度），但是没有一个正$m$边形的内角的度数是252的约数；取2个，则还差$360-108\times2=144$（度），这恰好是正10边形的内角，取3个，则还差$360-108\times3=36$（度），也不可能满足；取大于3个也显然不可能。
因此得到结论：当$n$和$m$中至少有一个为3或4或6时，或者当$n$和$m$中一个等于5另一个等于10时，有解，否则无解，时间复杂度为
$O\left(T\right)$。
##1002
考虑从高位到低位贪心，对于每一位，如果x，y只有唯一的取法，那么只能这么取；否则贪心地必须使答案的这一位等于1。如果x，y都是0，1都能取，则设这是从右向左数第len位，因为x，y能取的值一定都是连续的一段，因此x，y的后len位都能取0111...1（len-1个1）和1000...0（len-1个0）（否则做不到从右向左数第len位都能取0,1）。也就是说，后len位的贡献一定能达到可能的上界111...1（len个1）。此时不必继续考虑后面的位。
如果x，y在这一位并不是0,1都能取，那么由于要使得答案的这一位等于1，也只有唯一的取法。
至此，这一位考虑完毕，然后根据选取的方案，修正一下x和y的范围，然后对后一位做即可。
##1003
先枚举$k$，将所有$A_{i\times k}$（$i$是正整数且$i\times k<=n$）取下来存到$B_i$，于是将原问题转化成了下述问题：对于给定的正整数序列
$B_1,B_2,...,B_{\lfloor\frac{n}{k}\rfloor}$，求出连续的一段，使得这段的和值乘以这段的最小值的结果最大。
我们可以枚举最小值，设其在第$i$位出现，此时我们只要和值最大就可以了。设$B_i$向左第一个小于$B_i$的数是$l$（若没有则$l=0$），向右第一个小于$Bi$的数是$r$（若没有则$r=\lfloor\frac{n}{k}\rfloor+1$）。
则保证最小值不变的最大和值是$B_{l+1},B_{l+2}...B_{r-1}$这段。可以使用单调栈这种数据结构来在$O(\lfloor\frac{n}{k}\rfloor)$的复杂度下计算对于每个$i$的$l$和$r$，枚举最小值出现位置及更新答案的复杂度也是
$O(\lfloor\frac{n}{k}\rfloor)$。
再考虑外层的枚举k这一部分，总复杂度为$O\left(1+\frac{n}
{2}+...+\frac{n}{n}\right)$即$O(n\times(1+\frac{1}{2}+...+\frac{1}{n}))$，由于调和级数$1+\frac{1}{2}+...+\frac{1}{n}$为$logn$级别，因此时间复杂度为$O\left(nlogn\right)$。
##1004
不妨令$n\leq m$。
对于这一题，我们可以将所求的有多少对正整数对的最大公约数不为完全平方数转化为有多少对最大公约数为完全平方数。
那么我们设函数$F\left(x\right)$，当且仅当$x$为完全平方数时函数值为1，否则函数值为0。那么
$Ans=\sum_{i=1}^n\sum_{j=1}^mF\left(\gcd\left(i,j\right)\right)$
设$d=\gcd\left(i,j\right)$，那么
$Ans=\sum_{i=1}^n\sum_{j=1}^mF\left(d\right)$。
然后我们推一下这个式子：
$Ans=\sum_{d=1}^nF\left(d\right)\times\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\left[\gcd\left(i,j\right)=1\right]$
$=\sum_{d=1}^nF\left(d\right)\times\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|i,t|j}\mu\left(t\right)
=\sum_{d=1}^nF\left(d\right)\times\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu\left(t\right)\times\lfloor\frac{n}{dt}\rfloor\times\lfloor\frac{m}{dt}\rfloor$
然后我们设$G=dt$，则$Ans=\sum_{G=1}^n\left(t\right)\times\lfloor\frac{n}{G}\rfloor\times\lfloor\frac{m}{G}\rfloor\times\sum_{t|G}\mu\left(t\right)\times F\left(\frac{G}{t}\right)$
然后我们设$g(x)=\sum_{t|x}\mu\left(t\right)\times F\left(\frac{x}{t}\right)$,则$Ans=\sum_{G=1}^n\left(t\right)\times\lfloor\frac{n}{G}\rfloor\times\lfloor\frac{m}{G}\rfloor\times g(G)$。
那么这道题的解法就出来了，如果我们已经确定$g$函数的前缀和，那么就只需要类似莫比乌斯反演的方法$O\left(\sqrt{n}\right)$算一下即可。
现在我们来看如何求$g$函数，这肯定需要预处理。有这个函数的表达式我们可以进行分类讨论，可以求出$g\left(x\times p\right)$（$p$是质数且不为$x$的约数）与$g\left(x\right)$的关系然后欧拉筛。
上述算法的总时间复杂度是$O\left(m+T\sqrt{n}\right)$。
不过有另一种比较暴力的解法就是枚举$n$范围内的完全平方数然后暴力求$g$函数，这个时间复杂度是O(跑得过)。我测了一下$10^7$范围内的运算次数也就是$1.7\times10^7$次左右运算，是可以应付的。
##1005
对于求第$k$大的问题，我们可以通过在外层套一个二分，将其转化为求不小于$mid$的有多少个的问题。
接下来我们讨论如何求树上有多少条折链的长度不小于$k$。
我们考虑常规的点分治（对于重心，求出其到其他点的距离，排序+单调队列），时间复杂度为$O(nlog^2n)$，但是这只能求出普通链的数量。
我们考虑将不属于折链的链容斥掉。也即，我们需要求出有多少条长度不小于$mid$的链，满足一端是另一端的祖先。设有一条连接$u,v$的链，$u$是$v$的祖先。
我们设$d\left[i\right]$为从根到$i$的链的长度，然后枚举$v$，然后计算在从根到$v$的链上，有多少个点$i$满足$d\left[v\right]-dist\left[i\right]\geq mid$也即$d\left[i\right]\leq d\left[v\right]-mid$。
我们可以按照dfs序访问各结点，动态维护从根到其的链上各$d$值构成的权值树状数组，就能够计算这种链的数量。时间复杂度为
$O\left(nlogn\right)$。
因此求长度不小于$mid$的折链数量可以在$O\left(nlog^2n\right)$的时间复杂度内完成。再套上最外层的二分，总时间复杂度为
$O\left(nlog^3n\right)$。
$n$的范围是50000，时限3s，卡卡常数就过去了（本行划线
由于在点分治中，复杂度中第二个$logn$的瓶颈在于排序。由于每次排序都是对相同的数排序，因此我们可以考虑将点分治+排序作为预处理，每次二分的时候只要做单调队列部分即可。
上述做法的总时间复杂度为$O\left(nlog^2n\right)$。
