「Luogu P3409」值日班长值周班长 解题报告

题面

解题思路

数学与 $Ex\_gcd$

分析

根据题意，我们可以列出如下的方程组，设 $w$ 为周数，$bit$ 为离这周的周五还有几天

$$\begin{equation} \left\{ \begin{aligned} (5w-bit)\%n=m\ \ \ \ \ \ (1)\\ w\%p=q\ \ \ \ \ \ \ (2) \end{aligned} \right. \end{equation}$$

先将 $(2)$ 转换形式得：

$$w=px+q\ \ \ \ \ \ (3)$$

将 $(3)$ 代入 $(1)$ 得：

$$(5px+5q-bit)\%n=m\\$$ $$5px+5q-bit=ny+m\\$$

整理得：

$$5px+ny=m-5q+bit\\$$

令：

$$\begin{equation} \left\{ \begin{aligned} a=5p\\ b=n\\ c=m-5q+bit \end{aligned} \right. \end{equation}$$

原式就可以变成：

$$ax+by=c$$

这样的话，$x$ 的值就可以通过 $Ex\_gcd$ 得出一个最小正整数解，那么也就可以得出 $w$ 的值，从而得出最小满足条件的天数

最后通过枚举 $bit$ 来检验每个解即可

Warning

注意范围以及输出格式，每周只有五天，不要算周末的时间

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
LL n,m,p,q,a,b,c,d,x,y,ans,res;
inline LL Ex_gcd(rll a,rll b,rll &x,rll &y) {
    if(!b){x=1,y=0;return a;}
    rll d=Ex_gcd(b,a%b,y,x);
    y-=a/b*x;return d;
}
int main()
{
    rint i;
    while(~scanf("%lld%lld%lld%lld",&n,&m,&p,&q)) {
        a=5*p,b=n,c=m-5*q,ans=-1;//不想赋inf
        d=Ex_gcd(a,b,x,y),a/=d,b/=d;
        for(i=0;i<5;i++) {//枚举
            if((c+i)%d) continue;//有没有解
            res=((x*(c+i)/d%b)+b)%b;//得出最小正整数x
            res=res*5*p+5*q-i;//得出天数
            if(~ans) cmin(ans,res);
            else ans=res;
        }
        if(~ans) printf("%lld\n",ans);
        else printf("Orz mgh!!!\n");
    }
    return 0;
}