#P10443. [2021年联测]上进心
[2021年联测]上进心
上进心
题目描述
有 个工作小组,第 天第 组的工作量为 ,每天按如下规则同时更新:
每个月有 天,每过 天的月底,在当天的日常更新之后,各组额外加上 ,并记录各组工作量对 取模的值。
公司成立于一个月底,初始记录为 ,这一天不额外加 。以后每个月底都按上述规则增加额外工作量。
给定某次月底记录 ,求它最早可能是成立后多少个月的记录,允许为 。若 个月以内不存在符合全部分量的记录,输出 。
保证若 ,则第一个月月底第一组的工作量与 模 不同。
输入格式
第一行三个整数 。
第二行 个整数 。
第三行 个整数 。
第四行 个整数 。
输出格式
输出一个整数,表示最少月数;不存在不超过 10^10 的答案时输出 −1。
样例 1 输入
3 3 2
1 2 3
3 2 1
5851 73562 513993
样例 1 输出
4
样例说明
初始工作量为 。
第一个月:
$$(2,6,12)\to(4,16,40)\to(8+3,40+2,120+1)=(11,42,121).$$第二个月:
$$(22,106,348)\to(44,256,952)\to(88+3,600+2,2504+1)=(91,602,2505).$$第三个月月底为 ,第四个月月底为 ,所以答案为 。
数据范围
全部数据满足 ,,,。
原 PDF 将 的下界也写为 ,但样例含 、,此处允许样例中的 。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 15 | ,性质 A |
| 2 | ,性质 A | |
| 3 | 性质 A | |
| 4 | 20 | |
| 5 | 35 | 无 |
性质 A:若有答案,保证最少月数不超过 。
附加样例 2、3 分别满足子任务 2、5 的限制。