PE407&&PE451

嘛虽然说不宜贴PE题解……
不过既然没啥人看大概贴了也没关系?毕竟是比较简单的题目……451的solvers都快250+了

做题做不下去来看PE……然后发现了最后一页的可做题……过的人数这么多肯定不是啥难题?
题意:

407

定义l(n)为最大的a<n满足
例如l(6)=4

451

定义l(n)为最大的a<n满足
例如l(20)=11

SOL

这种题目直接上就好了……
两题很像就先看407……
首先如果
那么n的任意约数d……肯定也满足这一点:

所以我们对n分解质因数……接下里我们仅考虑这种情况
那么的解……显然只有两个……a=1或a=0
理由是……
如果
那么
那么
如果a与a-1都不整除p^k
那么显然的……(a-1)*a不整除p^k

所以这个特殊的方程只有两个解……

接下来考虑推广……对n分解质因数之后……设n有k个质因子……那么我们就有若干同余方程
a = 0或1 mod p1^q1
a = 0或1 mod p2^q2
...
a = 0或1 mod pk^qk
我们2^k暴力枚举解……然后中国剩余合并答案……得到的最大的a就是l(n)的答案了……

这样子看上去时间复杂度很高……但实际上k是很小的……大部分时间都很小……
实际上是能接受的……
然后跑一会就能得到解了……

要是爆long long了当我没说……

然后451几乎就是一样的……也是暴力CRT

比这样暴力更好的做法?抱歉我不会....

Comments

comments powered by Disqus