luogu#P1773. 符文之语

    ID: 5831 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划dpNOI 导刊枚举暴力递推

符文之语

题目背景

传说中珠穆朗玛峰下有座古代人修建的神庙,神庙的地下室里有古代王室的遗产,但数千年来从未有人到达过……探险者小 FF 一直梦想成为世界上最富有的人和最杰出的探险家并被永载史册。在证明了这个洞确实存在后,小 FF 做好了充足准备,来到了神庙。

题目描述

当小 FF 来到神庙时,神庙已经破败不堪了。但神庙的中央有一个光亮如新的石台。小 FF 走近石台,发现石台上有一个数串,而数串的上方刻着一串古老的符文之语。精通古符文之语的小 FF 不费吹灰之力就读懂了文章的意思,其大意是:

对于石台上的一串数字,你可以在适当的位置加入乘号(设加了 kk 个,当然也可不加,即分成 k+1k+1 个部分),设这 k+1k+1 个部分的乘积(如果 k=0k=0,则乘积即为原数串的值)对 mm 的余数(即 mod m\bmod\ m)为 xx

现求 xx 能达到的最小值及该情况下 kk 的最小值,以及 xx 能达到的最大值及该情况下的 kk 的最小值(可以存在 xx 的最小值与最大值相同的情况)。

小 FF 还知道,如果他找到了正确的答案,那么就可以通往神庙的下层了。但这个问题似乎不太好解决,小 FF 就找到了你,并答应找到财宝以后和你二八分(当然你拿二……)。

输入格式

第一行为数串,且数串中不存在 00

第二行为 mm

输出格式

四个数,分别为 xx 的最小值和该情况下的 kk,以及 xx 的最大值和该情况下的 kk,相邻两个数之间用一个空格隔开。

4421
22

0 1 21 0

提示

LL 表示字符串的长度。

  • 对于 30%30\% 的数据:2L502 \le L \le 50
  • 对于 100%100\% 的数据:2L10002 \le L \le 10002m502 \le m \le 50

NOI 导刊 20102010 提高(0202