自动搬运

查看原文

来自洛谷，原作者为

	CodyTheWolf ACM在役的小动物！qwq

搬运于2025-08-24 21:48:42，当前版本为作者最后更新于2018-12-17 19:57:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

来自攻略组成员的首发题解：

---

开头小广告：自己做的一个模板库OwO

---

算法考察：exGCD的最小正整数解

思路：

相信很多同学读完题都会列出这样的同余方程（或许只有本蒟蒻这样干qwq）：

$\frac{nx+m}{7}\equiv q (mod p)$

（x未知）

首先，这个题目描述有坑。实际上一周的有效天数只有5天。。。（而不是7）

其次，$q$和$m$的位置应该是$q-1$和$m-1$，因为值日和值周的同学都是从第1个开始的，而不是第0个。

再者，这里面有个整除，在同余方程里面太难搞了，我们考虑换个表达方式：

$nx+(m-1)\equiv py+(q-1)+i(mod 5)$

（x，y未知）

考虑到在值周同学的任期范围内，轮到值日的同学就行，但方程左边如果不加i的话，那么右边代表的只是某周的第一天，但是其他天数应该也要考虑上，因此加一个i，i的取值应该是$[0,4]$，

那我们只需要知道一组最小非负整数解x，y，$nx+(m-1)$（这里有坑注意看到题解最后）就是我们的答案啦。

诶？貌似就是我们的exGCD板子！但是还有一个未知数i怎么搞呢？范围太小啦，枚举就好，于是我们化式子：

(为了方便，让$m$和$q$一开始就减去1）

$nx-5py=5q-m+i$

但是普通的exGCD x，y是可负的，我们怎么把它转化为最小非负整数呢？（会的dalao可以跳过分割线内的内容了qwq）

---

关于exGCD的最小正整数解法：

对于方程：

$ax+by=c$

$x'=x+tb$，$y'=y-ta$也是一组解：

因为：

$ax'+by'=c$

$a(x+tb)+b(y-ta)=c$

$ax+tab+by-tab=c$

$ax+by=c$

他们是等价的。

所以我们考虑求得一个**最大的$t$**使得x，y都是非负整数解就好。

这里的$t=b/gcd(a,b)$，留给读者自行思考（而不是直接记结论）。

---

本题另外的坑点：

1.我们最终的答案并不是$nx+m$，而是$nx+m+1$，不要忘了我们的$m$是-1过的，因为实际上开始不能按照第0天算，而应该按照第1天算。

2.卡精度：某些变量需要__int128才能通过（建议自己思考一下到底是哪些）

3.$c$可能为0，此时我们需要特判，答案就是$m$（m没有被-1过的时候），想想为什么？

个人推荐难度（一次AC）：省选/NOI-

理由：exGCD+卡精度+思维+不低的细节复杂度。

CODE：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef long long int128;

LL n, m, p, q;

inline void Write(__int128 x)
{
    if (x > 9)
        Write(x / 10);
    putchar(x % 10 + '0');

    return;
}

inline __int128 exGCD(__int128 a, __int128 b, __int128 &x, __int128 &y)
{
    if (!b)
        return x = 1, y = 0, a;

    __int128 gcd = exGCD(b, a%b, x, y), tx = x;
    x = y, y = tx - (a / b) * y;

    return gcd;
}

inline __int128 Max(__int128 x, __int128 y)
{
    return x > y ? x : y;
}

inline __int128 Min(__int128 x, __int128 y)
{
    return x < y ? x : y;
}

signed main(void)
{
    while (scanf("%lld %lld %lld %lld", &n, &m, &p, &q) != EOF)
    {
        m--, q--;
        __int128 ans = -1;

        for (int i = 0; i < 5; i++)
        {
            __int128 a = n, b = 5 * p, c = 5 * q + i - m, x, y;

            if (c == 0)
            {
                ans = ans == -1 ? m : Min(ans, m);
                continue;
            }

            __int128 gcd = exGCD(a, b, x, y);
            if (c % gcd)
                continue;

            x *= c / gcd;
            __int128 t = b / gcd;
            x = (x % t + t) % t;

            __int128 temp = n * x + m;

            ans = ans == -1 ? temp : Min(ans, temp);
        }

        if (ans == -1)
            puts("Orz mgh!!!");
        else
            Write(ans + 1), putchar('\n');
    }

    return 0;
}