team2012-D1-sol-0009

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
给出下面 4 个函数:
 * g(x) = x^(x/2)
 * h1(x) = x / m1 * m1 + ( x + s1) % m1
 * h2(x) = x / m2 * m2 + ( x + s2) % m2
 * f(x) = g( h2( g( h1( g( x ) ) ) ) )
然后再给出一坨x和f(x), 让你求 s1, m1, s2, m2 这四个参数.

=== 数据范围 ===
 * 0 < s1, m1, s2, m2 < 345678

=== 解题思路 ===
这题最直接的想法就是枚举, 而且 sample 已经给出了很多组数据, 就是要让你利用这些数据来算出这 4 个参数, 所以时间范围可以适当放宽, 比如半小时或者一小时跑出来都是可以接受的. 当然 345678^4 这样的枚举肯定会超时, 但是平方级别 (345678^2) 的复杂度就可以接受了. 于是就考虑如何在枚举 s1 和 m1 (s2 和 m2) 的情况下验证是否有合法解.

其实我不是很懂为什么在确定 s1 和 m1 的情况下, s2 和 m2 有多解也是不合法的... 我是照着猛犸学长的思路写完程序然后算出来...

题目大意

给出下面 4 个函数:

• g(x) = x^(x/2)
• h1(x) = x / m1 * m1 + ( x + s1) % m1
• h2(x) = x / m2 * m2 + ( x + s2) % m2
• f(x) = g( h2( g( h1( g( x ) ) ) ) )

然后再给出一坨x和f(x), 让你求 s1, m1, s2, m2 这四个参数.

数据范围

• 0 < s1, m1, s2, m2 < 345678

解题思路

这题最直接的想法就是枚举, 而且 sample 已经给出了很多组数据, 就是要让你利用这些数据来算出这 4 个参数, 所以时间范围可以适当放宽, 比如半小时或者一小时跑出来都是可以接受的. 当然 345678^{4 这样的枚举肯定会超时, 但是平方级别 (345678}2) 的复杂度就可以接受了. 于是就考虑如何在枚举 s1 和 m1 (s2 和 m2) 的情况下验证是否有合法解.

其实我不是很懂为什么在确定 s1 和 m1 的情况下, s2 和 m2 有多解也是不合法的... 我是照着猛犸学长的思路写完程序然后算出来...