2018 China Collegiate Programming Contest Final (CCPC-Final 2018)

Problem A

Solved by Xiejiadong. 00:12 (+1)

温暖的排序签到。

+1 是因为煞笔了。

Problem B

Solved by Kilo_5723. 04:20 (+)

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Xiejiadong && Weaver_zhu. 00:33 (+1)

题意：求一个 $n\times m$ 的矩阵里面能选出多少对矩形，满足前一个被后一个包含的关系。

题解：观察一维线段被包含的情况，显然答案为 $\left ( _{n+1}^{4} \right )$，那么二维的情况就是乘起来。

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 03:01 (+1)

Problem J

Unsolved.

Problem K

Solved by Weaver_zhu. 03:53 (+10)

题意：随机在$[10^5, 10^9]$之中选一个$x$，然后选出小于$x$的最大质数$p$，不小于$x$的最小质数$q$，令$n=p \cdot q \;\; flag^{2^{30}+3} \equiv c (mod \; x)$现给定$x,c$求$flag$。

题解：素数还是挺多的，显然我们可以在$\sqrt{x}$附近找出$p,q$，然后$phi(x)$就出来了，然后求$2^{30}+3$关于$phi$的逆元$inv$，求出$c^{inv} \mod x$就是答案。嗯，看起来就这么简单。

心态崩了：求逆元的时候模数大于$10^9$要快速乘，然后快速乘被卡了。场上反复更换找素数的方法以为算法假了。但是组成$x$的两个质因数最大也在$10^9$附近，于是先在$p,q$模数下求出逆元再合回去。测试下来原6s数据现在跑1s。

Problem L

Solved by Xiejiadong. 03:10 (+2)

题意：给出一个数，将其分成六个质数相加的情况。

题解：首先一个数的周围，很容易找到一个质数。我们要找到一个质数，使得比这个数小至少 $20$ 。

然后，如果减去这个质数以后是奇数，则剩下的三位为$2,2,3$；如果是偶数，剩下的三位为$2,2,2$。

这样可以保证最后剩下的是一个偶数，并且$>2$，然后利用哥德巴赫猜想，找到剩下的两个质数即可。