打扰一下，比赛后我删了一句话就AC了，对比之下，还是不明白，可能您错了。就是我感觉p可以是k的因子啊，因为在一方出完之前都是轮出的，所以即便是素数也得先验证是不是自己先走完吧。。。。呜呜，反正我就是这样WA的。代码： http://www.cnblogs.com/hua-dong/p/8447768.html 。
然后特别操蛋的是maxn<=2倍1e6，我觉得数据太水了吧。都是小于1e6，然后我以为和<=1e10左右。然后我就以为我是以为这个WA了。
2018.2 月赛题解
oxx1108 edited 6 年，9 月前
A 坑爹的售票机
首先可以贪心直接计算出对于每次买 $i$ 张最少所需要的纸币数，这样就转换为一个背包问题。Hard 由于 $n$ 太大，不能直接 DP。
但 $k$ 较小，因此 $2520$ 张票的最优解一定为通过性价比最高的方式买。因此最终答案为 DP 算到 $\min(n, n \bmod 2520+2520)$（每种买票方式需要通过 DP 算的最多不超过 2520 张，若超过 2520 张则这 2520 张可以按性价比最优方式买，因此最多 DP 到 $k!k$ 即可），再加上剩余若干份 2520 张票。卡了几个假得不行的算法，优秀的假算法可能也能过……
验题人野鸡解法：大部分票肯定是 $m$ $(1 \le m \le k)$ 张一买的，枚举 $m$。然后，剩下的票直接 DP 算。大部分是多少呢？就取 $n-1000$ 好了。证明？不会……
B 无聊的游戏
比较裸的 SG 函数，每次操作后等于将一棵树拆为若干棵树，可将一棵树看为 $Nim$ 问题里的一堆石子，因为相互独立的树之间没有联系。直接暴力算会超时，因此需要对树 Hash 一下再记忆化。
还有一种很套路的做法，就是记忆化搜索，对于点状压一下记录状态，然后保存必胜态和必败态也可以，复杂度 $O(2^n n)$，足已通过。
C 贪吃的xjj和贪心的oxx
无论什么情况答案都为 Yes，方法为将原序列从大到小排序，贪心地放两堆，每次往少的一堆里放新的一盒，最终取少的一堆即可。
D 黑心的出租车
因为题目保证无环，因此必为树或森林。
当图为一棵树时，答案为 $0, 2(n-1)$。
当图为森林时，出租车次数判一下联通块即可，其实答案就是 $n-m$。而巴士站数，对于每个联通块，需要 $2$ 倍边的数量减去树的直径，然后求和即可。
注意慎用 memset，初始化仅需 DFS 所需要用的点，不然会 TLE。
E 出老千的xjj
当牌总数小于等于 $k$ 时，只需一张一张出即可，因此答案为 $0$。
当牌总数大于 $k$ 时，需要每次出 $x$ 张，且 $x$ 不整除 $k$，即加上万能牌后所有牌数量的$gcd$ 要不为 $k$ 的约数。
对于每次枚举的 $p$，通过前缀和可以求出数量在 $(p\cdot i,p(i+1)]$ 之间堆数的个数 $num$ 以及总数量和 $sum$，那么需要 $num \cdot p(i+1)-sum$ 张万能牌，最后求和即可。总复杂度 $O(n \log n)$。前缀和数组注意开到 $2 \cdot 10^6$。
还可以进行进一步优化：只需要枚举所有素数即可，对于 $k$ 的素因子 $p$，则取 $p^i$，最小的 $i$ 使得 $p^i$ 不能整除 $k$。
F 回家咯
三个方程可以解出 Xiamen 到中转站，中转站到 xjj 家和中转站到 oxx 家的时间，只要都为正数即有解，否则 Wrong。
Comments
当然可以啊，但是这可以归纳到第一种情况，通过计算可以知道需要sum(xi) / p <= k / p，即sum(xi) <= k。因为操作是增加sum的，所以原来sum就大于k的话，sum不会再变得小于k，所以可以归纳到第一种。我看了你的代码，不知为什么你的xx是n。
Cases里有大于1e6的啊，但是不超过2e6。