模拟赛
T1
题意很简单，就是给定n,求：
\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}\gcd(i,j)
这是一道数论题，看上去和洛谷P2158仪仗队有点像（其实转换一下就是那题），想想能不能用筛法（欧拉筛）做出来。令a[i]为i的贡献，为
\sum\limits_{j=1}^{i-1}\gcd(i\times p,j)
用欧拉筛做出来就意味着我们需要找到a[i*p]，a[p]，a[i]间的关系（p为i \times p的最小质因子）。
为了方便计算，先将a[i]转化为
\sum\limits_{j=1}^{i}\gcd(i\times p,j)
最后统计答案时减去i即可。
于是有：
\begin{aligned}\scriptstyle a_{i\times p}=\sum\limits_{j=1}^{i\times p}\gcd(i\times p,j)&\scriptstyle=\sum\limits_{j=1}^{i\times p}\gcd(i\times p,j)[p\nmid j]+\sum\limits_{j=1}^{i\times p}\gcd(i\times p,j)[p|j]\\&\scriptstyle =\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p\nmid j]+\sum\limits_{j=1}^{i\times p}p\times \gcd(i,j)[p|j]\\&\scriptstyle=\sum\limits_{j=1}^{i\times p}\gcd(i,j)-\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p|j]+\sum\limits_{j=1}^{i\times p}\gcd(i\times p,j)[p|j]\\&\scriptstyle=p\times a_i-\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p|j]+\sum\limits_{j=1}^{i\times p}\gcd(i\times p,j)[p|j]\\&\scriptstyle=p\times a_i-\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p|j]+p\times\sum\limits_{j=1}^{i\times p}\gcd(i,j/p)[p|j]\\&\scriptstyle=p\times a_i-\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p|j]+p\times\sum\limits_{j=1}^{i}\gcd(i,j)\\&\scriptstyle=p\times a_i-\sum\limits_{j=1}^{i\times p}\gcd(i,j)[p|j]+p\times a_i\end{aligned}
接下来分类讨论：
如果i\times p为质数：
显然
a[i\times p]=2i-1
如果i为合数
当p\nmid i时：
\begin{aligned} a_{i\times p}&=p\times a_i-\sum\limits_{j=1}^{i\times p}\gcd(i,j/p)[p|j]+p\times a_i\\& =p\times a_i-\sum\limits_{j=1}^{i}\gcd(i,j)+p\times a_i\\& =p\times a_i-a_i+p\times a_i\\& =(2p-1)a_i\end{aligned}
当p|i时：
\begin{aligned} a_{i\times p}&=p\times a_i-p\times\sum\limits_{j=1}^{i\times p}\gcd(i/p,j/p)[p|j]+p\times a_i\\&=p\times a_i-p\times\sum\limits_{j=1}^{i}\gcd(i/p,j)+p\times a_i\\&=p\times a_i-p\times a_{i/p}+p\times a_i\\&=2pa_i-pa_{i/p}\end{aligned}
综上，我们有：
a_{i\times p}=\begin{cases}2i-1&i为质数\\(2p-1)a_i&i为合数且p\nmid i\\2pa_i-pa_{i/p}&i为合数且p|i\end{cases}
于是我们就可以用欧拉筛愉快地递推了。
T2
状压DP板子（赛时被卡了一下）
不会状压的戳这里
T3
T4
原来是换根DP，赛时被概率绕进去了，难度还好。
（注意判断除数是否为0，否则会输出“-nan”）
PS
在本blog上写latex对低血压有神奇疗效
本blog编辑器喜欢的食物：代码、反斜杠、"$"