题解 P3409 【值日班长值周班长】

· · 题解

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

开头小广告：自己做的一个模板库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

因为： ### $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;
}