luogu P3409 值日班长值周班长 exgcd

LINK：值日班长值周班长

题目描述非常垃圾。

题意：一周5天每周有一个值周班长每天有一个值日班长值日班长日换值周班长周换。

共n个值日班长 m个值周班长 A是第p个值日班长 B是第q个值日班长问最早是哪一天使得值日班长为A且值周班长为B.

显然是一个类似于方程组的题目可以列出方程设是第x天.

\((x-p)\mod n=0\)

\(\lceil\frac{x}{5}\rceil \mod m=q-1\)

整到一个方程里就是 x=ny+p.

\(\lceil\frac{ny+p}{5}\rceil \mod m=q-1\)

解出来y即可。发现向上取整非常的不人性。

考虑到\(\frac{ny+p+bit}{5}==\lceil\frac{ny+p}{5}\rceil\)

枚举一下bit(0<=bit<=4)这样向上取整就可以被去掉解同余方程即可。

有点晕了。。。写挂了。咕掉

ll T,n,m,p,q,xx,yy;

ll ans;

inline ll exgcd(ll a,ll b)

{

	if(!b){xx=1;yy=0;return a;}

	ll d=exgcd(b,a%b);

	ll zz=xx;xx=yy;yy=zz-a/b*yy;

	return d;

}

signed main()

{

	freopen("1.in","r",stdin);

	while(gt(n)==1)

	{

		gt(p);ans=0;

		gt(m);gt(q);if(q==m)q=0;

		rep(0,4,i)

		{

			ll a=n,b=5*m;

			ll c=((5*q-p-i)%b+b)%b;

			ll gcd=exgcd(a,b);

			if(c%gcd)continue;

			ll mod=b/gcd;

			xx=(xx%mod+mod)%mod;

			xx=xx*c/gcd;

			ll now=xx*n+p;

			if(!ans)ans=now;

			else ans=min(ans,now);

		}

		if(ans)putl(ans);

		else puts("Orz mgh!!!");

	}

	return 0;

}

巴特西

luogu P3409 值日班长值周班长 exgcd

最新文章

热门文章