T1无关

一道经典的容斥原理题目。 对于$3030\%$的数据，可以用暴力骗一波分。

对于$100100\%$的数据，L-R可以达到$10^{18}10^\{18\}$，对于暴力来说太大了。但是$k\le 20k\backslash leq\; 20$,相对来说是极小的。

于是我们想到了容斥原理：

$\mid A_1\cup A_2\cup \cdots \cup A_m\mid =\backslash left|A\_\{1\}\; \backslash cup\; A\_\{2\}\; \backslash cup\; \backslash cdots\; \backslash cup\; A\_\{m\}\backslash right|=$

在$[1,N][1,\; N]$内，由于$aa$数组内全部都是质数，是$a[i]a[i]$的倍数的数的数目为$\lfloor \frac{N}{a[i]}\rfloor \backslash left\backslash lfloor\backslash frac\{N\}\{a[i]\}\backslash right\backslash rfloor$，是$\mathrm{a}[\mathrm{i}],\mathrm{a}[\mathrm{j}]\backslash mathrm\{a\}[\backslash mathrm\{i\}],\; \backslash mathrm\{a\}[\backslash mathrm\{j\}]$的倍数的数的数目为$\lfloor \frac{N}{a[i]a[j]}\rfloor \backslash left\backslash lfloor\backslash frac\{N\}\{a[i]\; a[j]\}\backslash right\backslash rfloor$，以此类推。

枚举子集即可，复杂度为$\mathrm{\Theta }(k\cdot 2^k)\backslash Theta\backslash left(k\; \backslash cdot\; 2^\{k\}\backslash right)$，但必须对元素乘积超过$NN$的集合进行剪枝，这样跑起来是极快的。

PS: 本来出题人是打算$k\le 0\mathrm{，}2\le a_i\le 40k\backslash leq\; 0，\; 2\backslash leq\; a\_i\backslash leq\; 40$， 不保证质数，然后再去重的,但是要加一层lcm,既有可能求lcm的过程中爆炸，又会增加复杂度。考虑到这是小白赛，出题人最终还是保证质数，范围给到了$k\le 20\mathrm{，}2\le a_i\le 100k\backslash leq\; 20，2\backslash leq\; a\_i\backslash leq\; 100$。

T2范围

经典的柯西不等式：

$(\frac{1}{a_1}+\frac{1}{a_2}+\dots +\frac{1}{a_{n-1}}+\frac{1}{a_n})(a_1{x}_1^2+a_2{x}_2^2+\dots +a_{n-1}{x}_{n-1}^2+a_n{x}_n^2)=1\times (B-x^2)\ge \backslash left(\backslash frac\{1\}\{a\_\{1\}\}+\backslash frac\{1\}\{a\_\{2\}\}+\backslash ldots+\backslash frac\{1\}\{a\_\{n-1\}\}+\backslash frac\{1\}\{a\_\{n\}\}\backslash right)\backslash left(a\_\{1\}\; x\_\{1\}^\{2\}+a\_\{2\}\; x\_\{2\}^\{2\}+\backslash ldots+a\_\{n-1\}\; x\_\{n-1\}^\{2\}+a\_\{n\}\; x\_\{n\}^\{2\}\backslash right)=1\; \backslash times\backslash left(B-x^\{2\}\backslash right)\; \backslash geq$ ${(x_1+x_2+\dots +x_{\mathrm{n}-1}+x_{\mathrm{n}})}^2=(A-x{)}^2\backslash left(x\_\{1\}+x\_\{2\}+\backslash ldots+x\_\{\backslash mathrm\{n\}-1\}+x\_\{\backslash mathrm\{n\}\}\backslash right)^\{2\}=(A-x)^\{2\}$

最终问题转化到了 ：

求 $2x^2-2Ax+A^2-B\le 02\; x^\{2\}-2\; A\; x+A^\{2\}-B\; \backslash leq\; 0$ 的取值范围

利用二元一次方程的性质求解即可

T3水题

首先，满足给出公式的函数(数列)为: Fibonacci sequence.不了解的可以自行百度。

对于读入的$nn$，只要判断是不是斐波那契数就可以了:

(1)若不是，就是一个n皇后问题(位运算优化)

(2)若是， 就是一个进制转化的问题，随便做一下就过了

T4阶乘

我可能缺一道真签到题。 观察这个表达式我们发现o的个数即为该表达式的最终结果含有$1010$的几次方的因子。 我们就联想到了拆素数。 并且$1010$的$nn$次方都有一个通性:质因子只有$22$和$55$。 显而易见，最终结果中质因子$22$的个数远远大于$55$的个数。 所以这道题就是找因子$55$的个数。 由于是阶乘的连乘，后一个数a都比前一个数$(2-1)(2-1)$多乘了个$aa$。 我们的目标是找$55$的个数，也就是每五个一循环,更新每次乘上的$55$的个数。 思路很好想，剩下的就是看代码能力了。

T5面积

我可能是个胡诌高手呢。 首先扔一波尔约-格维也纳定理，即任意两个面积相等多边形能够通过有限次裁剪拼接得到:

结论1:任意两个正方形，可以拼接成一个大正方形。如图 结论2:任意多个正方形都可以拼接成一个大正方形。 证明:滚雪球，拿两个一拼，然后完了再拿两个一拼。最后就剩一个大正方形。

结论3:如果图形A能拼接成图形B，图形B能拼接成圄形C，则图形A也能拼接成圉形C。

结论4:如果圄形A能拼接成图形B,则图形B也能拼接成图形A。

结论5:若矩形的长宽之比小于4:1，则这个矩形可以拼接成正方形。

结论6:任意一个长宽之比超过4:1的矩形都能拼接成一个长宽比小于4:1 的矩形。

结论7:由5. 6推出，任意一个矩形可以拼接成一个正方形。

结论8:任意一个平行四边形都可以拼接成一个矩形。如图

结论9:任意一个三角形都能拼接成一个平行四边形。如图

结论10:任意一个四边形都可以拼接成一个正方形(以为任意一个四边形都可以又若干三角形组成)。

结论11:任意一个多边形都可以拼接成一个正方形(理由同上)。如图

于是，我们得到了一个更加疯狂的结论。 最终得到结论12，即就是波尔约-格维也纳定理:

任意两个面积相等的多边形，它们可以相互拼接得到。 由法卡斯.波尔约(Farks Bolyai)和保罗.格维也纳(Paul Gerwien)两位数学家分别在1833年和1835年证明。

一张方格纸上，上面画着纵横两组平行线，相邻平行线之间的距离都相等, 这样两组平行线的交点，就是所谓格点。如果取一个格点做原点$OO$，如图1，取 通过这个格点的横向和纵向两直线分别做横坐标轴0X和纵坐标轴$OYOY$，并取原来方格边长做单位长，建立一个坐标系。这时前面所说的格点，显然就是纵横两坐标都是整数的那些点。如图1中的$O\mathrm{.}P\mathrm{、}Q\mathrm{.}M\mathrm{、}NO.\; P、Q.\; M、N$都是格点。由于这个缘故， 我们又叫格点为整点。

一个多边形的顶点如果全是格点，这多边形就叫做格点多边形。有趣的是，这种格点多边形的面积计算起来很方便,只要数一下图形边线上的点的数目及图内的点的数目，就可用公式算出。

这个公式是皮克(Pick)在1899年给出的，被称为“皮克定理”，这是一个实用而有趣的定理。

给定顶点坐标均是整点(或正方形格点)的简单多边形，皮克定理说明了其面积$SS$和内部格点数目$nn$、边上格点数目$ss$的关系:

$S=n+\frac{s}{2}-1S=n+\backslash frac\{s\}\{2\}-1$ 又叫格点为整点。

(其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积)

所以，一个点阵的“最大生成图”的面积恒为 $\frac{M\times \mathrm{N}}{2}-1\backslash frac\{M\; \backslash times\; \backslash mathrm\{N\}\}\{2\}-1$， 可以利用向量叉积求 出三角形的面积，只需要判断这两个面积是否相等就可以了。

T6圆

我可能坑了一波做题人，Python 或java并不比C++好做多少，因为规律并不是$2^{n-1}2^\{n-1\}$。

这是一道欧拉公式题!

如果圆上只有一个点，圆内将不会产生任何线段,整个圆仍然是完整的一块。 图7显示的就是$nn$分别为$2\mathrm{、}3\mathrm{、}42、3、4$的情况。可以看到，圆分别被划分成了$2\mathrm{、}4\mathrm{、}82、4、\; 8$块。规律似乎非常明显:圆周上每多一个点，划分出来的区域数就会翻一倍。 事实上规律真的是这样吗?让我们来看看$n=5n=5$的时候(图8)。

果然不出所料，整个圆被分成了$1616$块，区域数依旧满足$2n-12n-1$的规律。此时， 大家都会觉得证据已经充分，不必再往下验证了吧。偏偏就在$n=6n=6$的时候，意外 出现了(圈9)。

此时，区域数只有$3131$个。那么，这个数列规律究竟是什么呢?这回，欧拉公式又帮上了大忙。圆周上每四个点交叉相连，就会在圆内产生一个交点，因此圆内共有$C_n^{4}C\_\{n\}^\{4\}$个交点，因此圆周上本身的 $nn$个点，可得图中的总顶点数$V=C_n^4+nV=C\_\{n\}^\{4\}+n$。圈内每个顶点的度数都为$44$，圆周上每个顶点度数都是$n+1n+1$，因此图中顶点的度数之和为$4C_n^4+n(n+1)4\; C\_\{n\}^\{4\}+n(n+1)$。由于每根线条都贡献了两个度，因而图中的总线条数就是$E=\frac{4C_n^4+n(n+1)}{2}=2C_n^4+\frac{n(n+1)}{2}E=\backslash frac\{4\; C\_\{n\}^\{4\}+n(n+1)\}\{2\}=2\; C\_\{n\}^\{4\}+\backslash frac\{n(n+1)\}\{2\}$。因此，图中的总区域数就是: $F=E-V+2=(2C_n^4+\frac{n(n+1)}{2})-(C_n^4+n)+2=C_n^4+\frac{n(n+1)}{2}+2F=E-V+2=\backslash left(2\; C\_\{n\}^\{4\}+\backslash frac\{n(n+1)\}\{2\}\backslash right)-\backslash left(C\_\{n\}^\{4\}+n\backslash right)+2=C\_\{n\}^\{4\}+\backslash frac\{n(n+1)\}\{2\}+2$

它可以写成$C_n^4+C_n^2+2C\_\{n\}^\{4\}+C\_\{n\}^\{2\}+2$，去掉圆外面那个无限大的区域，圆内部的区域数也就是$C_n^4+C_n^2+1C\_\{n\}^\{4\}+C\_\{n\}^\{2\}+1$。其实这个答案也不难理解:每画出一条新线段后，假如这条新线段与原来已有的线段产生了$kk$个新交点，那么圆内就会增加$k+1k+1$块区域。由于 没有话任何的线段时，圆内的区域数为$11$，因此最终总的区域数就是$11$加上所有交点的个数，再加上所有线段的数量，也就是$C_n^4+C_n^2+1C\_\{n\}^\{4\}+C\_\{n\}^\{2\}+1$了。

关键在于，$C_n^4+C_n^2+1C\_\{n\}^\{4\}+C\_\{n\}^\{2\}+1$又可以写成$C_{n-1}^4+C_{n-1}^3+C_{n-1}^2+C_{n-1}^1+1C\_\{n-1\}^\{4\}+C\_\{n-1\}^\{3\}+C\_\{n-1\}^\{2\}+C\_\{n-1\}^\{1\}+1$，也就是杨辉三角第n行的前5个数之和。由于杨辉三角前$55$行都没超过$55$个数，因此$nn$是小于等于5的正整数是，$C_{n-1}^4+C_{n-1}^3+C_{n-1}^2+C_{n-1}^1+1C\_\{n-1\}^\{4\}+C\_\{n-1\}^\{3\}+C\_\{n-1\}^\{2\}+C\_\{n-1\}^\{1\}+1$就相当于是杨辉三角第$nn$行所有数全部相加的结果。而杨辉三角第n行的所有数之和正好就是$2^{n-1}2^\{n-1\}$，于是便诞生 了数学中最具误导性的“违规律”。

PS: solution 摘自顾森《思考的乐趣:Matrix67数学笔记》之《30.欧拉公式的另类证法和出人意料的应用》，这大概是我目前读的最懂的一篇证明，写的简单易懂，而又不失严谨，比出题人高到不知哪里去了，所以摘了过来。

如有雷同，不是巧合;如有侵权,请联系Apojacsleam(QQ1729338463)删除。

T7异或

若一共有$kk$条鱼，考虑第$kk$条鱼，如果第$k-1k-1$条鱼睡着了，第$kk$条鱼可以肆 无忌惮地吃掉第$k-1k-1$条鱼，所以第$k-1k-1$条鱼不敢吃掉第$k-2k-2$条鱼，那么第$k-2k-2$条鱼 就可以肆无忌惮地吃掉第$k-3k-3$条鱼,以此类推,得到若鱼群数量为奇数,则第TbGx就可以肆无忌惮地吃食物，否则就不敢吃。 于是问题转化成了:求Fibnacci 数列前n项有多少项是奇数。 所以答案是：$\left[\frac{2}{3}n\right]\backslash left[\backslash frac\{2\}\{3\}\; n\backslash right]$。

T8最大公约数

用欧几里德算法求一下$gcd(a,b)gcd(a,b)$，然后用$lcm\ast gcd=a\ast blcm*gcd=a*b$求解即可。 由于数据范围，所以需要先约分。

T9区间

有多少人去写线段树板子了?在群里举个手可好?

这是一道前缀和的板子题。

因为Query操作在最后,且只有一次，所以只需要开一个数组记录所有的区间修改情况，最后用前缀和求解即可，时空复杂度都为$\mathrm{\Theta }(N)\backslash Theta(N)$。

需要说明的是，由于所有输入数据都在int内，所以不能保证int范围不会爆，只能开long long。 线段树需要开4倍空间，32M的空间会略显不足。

本来时间限制是15，为了照顾java选手，改成了两秒，不然卡线段树$\mathrm{\Theta }(n\log n)\backslash Theta(n\; \backslash log\; n)$还是可以的。

T10时间

我可能缺一道真签到题。 提前记录一天中所有的回文时间，打表模拟即可。 要注意，输入数据可能有前导o，也可能没有，C++选手可以用scanf("%d:%d",hour,min);来输入。