第一题显然是水题
变一下就变成
再变一下就变成
先筛出10000内的素数
然后直接拿h去分解质因数然后算一下x+1有多少种可能就可以了,
注意大于10000的素数需要特判,因为筛不掉(笑)
第二题一看连搜索都没想法…
第三题又是数学题,一开始还理解错题意了,是一行站mi个人而不是有mi行,如果不是看了数据范围特点说明了ai< mi的话,就要懵逼整场比赛了..
说明看题还是不过细心,草草扫过一眼就开始想
然后想到一个合并的思想,假如有一个m1,m2,a1,a2,那么我们考虑一个x使得
如果要合并这两个式子, 得出一个新式子,使得只要新式子满足,那么两个旧式子也满足.
首先想到的肯定是mod lcm(m1,m2), 那么余数如何确定呢?
设1,2种取法行数分别为x与y
我们知道m1x + a1 = m2y + a2,因为人数是固定的
那么移项得, m1x-m2y = a2-a1
m1, m2与右边是已知的,可以用拓展gcd解出x y
最后是因为处理模那里有问题, 得出来的人数有可能过大过小…..
只拿了5分,后来改了一下能拿60分,剩下40分是因为int64爆了…. 只要先把gcd(a,b)给div掉就能拿满分了.
zjq的方法也很巧妙, 虽然和暴力没啥区别… 但是谁叫人家M最大1000呢
第二题原来是一题区间DP