M04148: 生理周期

brute force, http://cs101.openjudge.cn/practice/04148

同

01006:Biorhythms

http://cs101.openjudge.cn/practice/01006/

人生来就有三个生理周期，分别为体力周期、感情周期和智力周期，它们的周期长度分别为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，在智力周期的高峰，人会思维敏捷，注意力容易高度集中。因为三个周期的长度不同，所以通常三个周期的高峰不会落在同一天。对于每个人，想知道何时三个高峰落在同一天。对于每个周期，会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。给定一个从当年第一天开始的天数，你的任务是输出从给定时间开始（不包括给定时间），下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同一天的时间是12，则输出2（注意这里不是3）。

输入

输入包含多组数据，每一组数据由四个整数组成，数据以-1 -1 -1 -1 结束。对于四个整数p, e, i和d，p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d是给定的时间，可能小于p, e或i。所有给定时间是非负的并且小于或等于365，所求的时间小于或等于21252。

输出

从给定时间起，下一次三个高峰同一天的时间（距离给定时间的天数）。

样例输入

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

样例输出

Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.

来源

East Central North America 1999

思路：思路大概就是找到取余各个周期之后都是高峰的数，且这个数要离给的天数最近，debug有两个点需要注意一个是范围应该到d+21252而不是21252，另一个是输出的格式，要仔细对比空格，大小写等等，要不然会浪费大量时间。

python

# 赵瑞瑞 城环学院
def shenglizhouqi():
    case=1
    while True:
        p, e, i, d = map(int, input().split())
        if p == e == i == d == -1:
            break
        
        # 算出出现再周期的那一天
        p_ = p % 23
        e_ = e % 28
        i_ = i % 33
        for a in range(d + 1, d+21253):
            if a % 23 == p_ and a % 28 == e_ and a % 33 == i_:
                print(f'Case {case}: the next triple peak occurs in {a-d} days.')
                case+=1
                break
shenglizhouqi()

从给定的时间点开始推，同时满足三个条件

python

num = 1
while True:
    p, e, i, d = map(int, input().split())
    if [p, e, i, d] == [-1, -1, -1, -1]:
        break

    # 从给定时间d起，下一次三个高峰同一天的时间.
    # p,e,i 接收到数据，分别对应周期取余，否则可能找到的不是d起的下一个.
    # p %= 23
    # e %= 28
    # i %= 33

    s = d + 1

    while (s - p) % 23 != 0 or (s - e) % 28 != 0 or (s - i) % 33 != 0:
        s += 1

    s -= d
    print(f'Case {num}: the next triple peak occurs in {s} days.')
    num += 1

没有用数学公式，直接一遍一遍加d了，计算机做加法真的好快

python

counter = 0
while True:
        p, e, i, d = map(int, input().split())
        if [p, e, i, d] == [-1, -1, -1, -1]:
          break
        counter +=1
        p %= 23
        e %= 28
        i %= 33
        origin = d
        d += 1
        while d % 23 != p or d % 28 != e or d % 33 != i:
            d += 1
        print(f'Case {counter}: the next triple peak occurs in {d-origin} days.')

思路：即求出最小的n，使得n%23=p，n%28=e，n%33=i，输出n-d.由于n-d不超过232833，建立一个长度为d+21253的全为0的列表，依次将满足x%23=p，x%28=e，x%33=i的dp[x]加1，最后一次循环时，若dp[x]=3且x不为0，则x就是所求的n，输出n-d即可

python

# 柯有为 24-工学院
m = 1
while True:
    p, e, i, d = map(int, input().split())
    if p == -1:
        break
    n = 0
    dp = [0] * (d + 21253)
    for x in range(p, d + 21253, 23):
        dp[x] += 1
    for x in range(e, d + 21253, 28):
        dp[x] += 1
    for x in range(i, d + 21253, 33):
        dp[x] += 1
        if dp[x] == 3 and x != 0:
            n = x
            break
    print(f"Case {m}: the next triple peak occurs in {n - d} days.")
    m += 1

用整除法可以判断周期是否相同，出现负数直接加上 21252 即可。

python

# 付耀贤 24信管系
n = 0
while True:
    a, b, c, d = map(int, input().split())
    n += 1
    if a + b + c + d >= 0:
        found = False
        for i in range(1, 21253):
            if (i - a) % 23 == 0 and (i - b) % 28 == 0 and (i - c) % 33 == 0:
                if i - d >= 0:
                    print(f"Case {n}: the next triple peak occurs in {i - d} days.")
                else:
                    print(f"Case {n}: the next triple peak occurs in {i - d + 21252} days.")
                found = True
                break
        if not found:
            print(f"Case {n}: No valid solution found within the range.")
    else:
        break

周期跳跃找数

python

num = 0

while True:
    p,e,i,d = [int(x) for x in input().split()]
    if p == -1:
        break

    p = p%23 + ((d-p)//23+1)*23
    e = e%28 + ((d-e)//28+1)*28
    i = i%33 + ((d-i)//33+1)*33

    while p!=e:
        if p<e:
                p += 23
        else:
                e += 28
    while e!=i:
        if i<e:
            if (e-i)%33 == 0:
                break
            else:
                i += ((e - i) // 33 + 1)*33
        if i>e:
            e += 23*28
    num += 1
    print("Case %d: the next triple peak occurs in %d days."%(num,max(e-d,i-d)))

同余是数论中的一个重要概念，它描述了两个整数在除以同一个正整数时余数相同的关系。具体来说，如果两个整数 a 和 b 除以正整数 m 的余数相同，那么我们说 a 和 b 在模 m 下同余，记作：a ≡ b(mod m)

利用中国剩余定理（Chinese Remainder Theorem, CRT）来直接求解这个问题。中国剩余定理可以帮助我们在给定模数的情况下，找到一个满足多个同余方程的解。

extended_gcd(a, b)：使用递归方式实现扩展欧几里得算法。返回最大公约数 gcd 以及满足 a⋅x+b⋅y=gcd(a,b) 的整数 x 和 y。

计算模逆元是数论中的一个重要概念，特别是在密码学和计算机科学中有着广泛的应用。模逆元的定义如下：
给定两个整数 a 和 m，如果存在一个整数 (x) 使得 $a \cdot x \equiv 1 \pmod{m} $ 那么 x 就被称为 a 模 m 的逆元，记作 $a^{- 1} (\mod m)$ 。
原理
模逆元存在的充要条件是 a 和 m 互质（即 $gcd (a, m) = 1$ ）。这是因为如果 a 和 m 不互质，那么不存在这样的 x 使得 $a \cdot x \equiv 1 (\mod m)$ 。
计算方法
扩展欧几里得算法 (Extended Euclidean Algorithm)
扩展欧几里得算法不仅能够计算两个整数的最大公约数，还能找到整数 x 和 y，使得 $ a \cdot x + m \cdot y = \gcd(a, m) $
如果 $gcd (a, m) = 1$ ，那么我们可以得到 $a \cdot x + m \cdot y = 1 $
将上式两边同时对 m 取模，可以得到 $ a \cdot x \equiv 1 \pmod{m} $
因此，x 就是 a 模 m 的逆元。
示例代码
下面是一个使用扩展欧几里得算法计算模逆元的 Python 实现：
python
def extended_gcd(a, b):
 if a == 0:
     return b, 0, 1
 else:
     gcd, x1, y1 = extended_gcd(b % a, a)
     x = y1 - (b // a) * x1
     y = x1
     return gcd, x, y

def mod_inverse(a, m):
 gcd, x, y = extended_gcd(a, m)
 if gcd != 1:
     raise ValueError(f"No modular inverse for {a} modulo {m}")
 else:
     # 确保结果为正数
     return x % m

# 示例
a = 3
m = 11
try:
 inv = mod_inverse(a, m)
 print(f"The modular inverse of {a} modulo {m} is {inv}")
except ValueError as e:
 print(e)
代码解析
extended_gcd(a, b)：
使用递归方式实现扩展欧几里得算法。
返回最大公约数 gcd 以及满足 (a \cdot x + b \cdot y = \gcd(a, b)) 的整数 x 和 y。
mod_inverse(a, m)：
调用 extended_gcd(a, m) 获取 gcd、x 和 y。
如果 gcd 不等于 1，则说明 (a) 和 (m) 不互质，抛出异常。
否则，返回 x % m 作为模逆元，确保结果为正数。
通过这种方法，我们可以有效地计算出模逆元，并且在实际应用中非常有用，尤其是在加密算法如 RSA 中。如果你有更多具体的问题或者需要进一步的解释，请告诉我！

python

# 计算最大公约数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# 计算最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 扩展欧几里得算法
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

# 计算模逆元
def mod_inverse(a, m):
    gcd, x, y = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError(f"No modular inverse for {a} modulo {m}")
    else:
        # 确保结果为正数
        return x % m

# 使用中国剩余定理求解
def find_next_triple_peak(p, e, i):
    m1, m2, m3 = 23, 28, 33
    M = lcm(lcm(m1, m2), m3)
    M1, M2, M3 = M // m1, M // m2, M // m3
    y1, y2, y3 = mod_inverse(M1, m1), mod_inverse(M2, m2), mod_inverse(M3, m3)

    n = (p * M1 * y1 + e * M2 * y2 + i * M3 * y3) % M
    return n, M

# 主程序
m = 1
while True:
    p, e, i, d = map(int, input().split())
    if p == -1 and e == -1 and i == -1 and d == -1:
        break

    # 找到从d开始的下一个三重峰值
    n, M = find_next_triple_peak(p, e, i)

    if n <= d:
        # 如果n小于d，我们需要加上最小公倍数
        n += M

    print(f"Case {m}: the next triple peak occurs in {n - d} days.")
    m += 1

此问题属于为同余方程问题。目标是找到一个最小的正整数 x 使得：

x≡p (mod 23)
x≡e (mod 28)
x≡i (mod 33)

在此基础上，求得的 x 应该大于给定的天数 d，并计算它与 d 的差值。

python

import math


# 计算最大公约数
# def gcd(a, b):
#     while b:
#         a, b = b, a % b
#     return a


# 计算最小公倍数
def lcm(a, b):
    return a * b // math.gcd(a, b)


# 计算模逆元
def mod_inverse(a, m):
    m0, x0, x1 = m, 0, 1
    if m == 1:
        return 0
    while a > 1:
        q = a // m
        m, a = a % m, m
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += m0
    return x1


# 使用中国剩余定理求解
def find_next_triple_peak(p, e, i):
    m1, m2, m3 = 23, 28, 33
    M = lcm(lcm(m1, m2), m3)
    M1, M2, M3 = M // m1, M // m2, M // m3
    y1, y2, y3 = mod_inverse(M1, m1), mod_inverse(M2, m2), mod_inverse(M3, m3)

    n = (p * M1 * y1 + e * M2 * y2 + i * M3 * y3) % M
    return n, M


m = 1
while True:
    p, e, i, d = map(int, input().split())
    if p == -1 and e == -1 and i == -1 and d == -1:
        break

    # 找到从d开始的下一个三重峰值
    n, M = find_next_triple_peak(p, e, i)


    if n <= d:
        # 如果n小于d，我们需要加上最小公倍数
        n += M

    print(f"Case {m}: the next triple peak occurs in {n - d} days.")
    m += 1

M04148: 生理周期 ​

M04148: 生理周期