首页 > 其他分享 >P4774 屠龙勇士 题解

P4774 屠龙勇士 题解

时间:2024-03-09 10:11:36浏览次数:15  
标签:P4774 pmod 题解 2x EXCRT 1x 屠龙 equiv

传送门

显然每一只龙对应了唯一的一把剑。用 multiset 可以求出每一把剑。于是题目就变成了:

\[\begin{cases}b_1x\equiv a_1\pmod {m_1}\\b_2x\equiv a_2\pmod{m_2}\\\dots\\b_nx\equiv a_n\pmod{m_n}\end{cases} \]

如果 \(b_i=1\),直接 EXCRT 即可。

现在 \(b_i>1\),还是以 EXCRT 的思路:

如何合并两个同余方程 \(b_1x\equiv a_1\pmod{m_1},b_2x\equiv a_2\pmod{m_2}\)?

\(b_1x=a_1+k_1m_1,b_2x=a_2+k_2m_2\)。

移项,\(b_1x+(-m_1)k_1=a_1,b_2x+(-m_2)k_2=a_2\)。

明显的扩欧,求出

标签:P4774,pmod,题解,2x,EXCRT,1x,屠龙,equiv
From: https://www.cnblogs.com/FLY-lai/p/18062312

相关文章

  • APatch常见问题解答
    常见问题解答什么是APatch?APatch是一种类似于Magisk或KernelSU的root解决方案,但APatch提供更多功能。APatch分别结合了Magisk方便易用的通过boot.img安装的方法,和KernelSU强大的内核修补能力。APatch与Magisk的区别?Magisk对启动映像中的ramdisk进行补丁,以修改init系统。而AP......
  • P6810 「MCOI-02」Convex Hull 凸包 题解
    分析推式子题。\[ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\tau(\gcd(i,j))\]对于\((i,j)\),若\(k\)是\((i,j)\)的因子,则\(k\)一定整除\(i,j\),所以有:\[\\\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\tau(i)\tau(j)\sum\limits......
  • CF1436E Complicated Computations 题解
    题目链接:CF或者洛谷关于\(mex\)问题是一个比较久远的问题,有很多经典的方法去解决。本题的\(mex\)是从正整数开始的,不要忽略掉。来讲讲常见的两种解决方案,首先回到题目所问,如果我们暴力地询问:\(1,2,3,4,.....mex\)是否都能由原数组构造出来,对于\(i\)如果它可以由原数组......
  • CF935D Fafa and Ancient Alphabet 题解
    讲一个很暴力的方法(为描述方便,下文\(a\)数组代表\(s1\),\(b\)数组代表\(s2\))。发现假如当前\(a_i\neb_i\),就不需要再向下枚举了,于是拥有了分类讨论的雏形。我们设\(inv\)代表进行到这一步的概率,可分为以下四种情况:\(a_i>0,b_i>0\)。此时假如\(a_i=b_i\),略过;若\(a_i>......
  • [HDU6647] Bracket Sequences on Tree 题解
    [HDU6647]BracketSequencesonTree题解一道纯靠自己推出来的换根\(dp+\)树哈希,写篇题解庆祝一下~~题意:给定一棵无根树,你可以任意选择根节点和遍历顺序,每次遍历时进入一个节点就标记一个(,离开一个节点就标记一个),问所有存在的括号序列有多少种,对998244353取模。先考虑根固......
  • CF contest 1935 Round 932 (Div. 2) A-D题解
    CodeforcesRound932(Div.2)A-D题解CodeforcesRound932(Div.2)绪言很菜,AB速度慢,卡在C,想DP,但是时间优化不下来,说服自己\(2\times10^3\)能过\(n^3\),D稍微简单,但是没看D,遂掉分。A.EntertainmentinMAC给你一个字符串\(s\)和一个偶整数\(n\)。你可以对它进行两种运......
  • 【教程】 iOS构建版本无效问题解决方案
     引言在进行iOS应用上架时,有时会遇到构建版本无效的问题,即通过XCode上传成功后,但在AppStoreConnect的TestFlight中无法显示构建版本,或者显示一会儿后就消失了。本文将介绍可能的原因分析,并提供解决问题的方法。问题描述最近一次上传新版本至AppStore后,发现在AppStoreCon......
  • [ARC157F] XY Ladder LCS 题解
    我们尝试给这个抽象题来一篇题解。思考过程还是很重要的。首先看了这个题,一看数据范围\(n\le50\),然后就不懂了,你告诉我这玩意可以状压??然后我们一顿乱想,发现如果\(n\)除以一个\(3\),那我们是不是就可以状压了。那怎么除以\(3\)呢。接着我们手玩一下样例,发现似乎这个答案......
  • [青少年CTF训练平台]web部分题解(已完结!)
    文章管理系统首先打开环境(>ω<。人)ZZz♪♪既然要做题,就要做全面了,图上说了,既然有假flag我就先找出来:假flag:打开vmware,使用sqlmap进行处理:sqlmap-uhttp://challenge.qsnctf.com:31645/?id=1--dbs记得中间的url换成自己的看到了六个可能:{*]ctftraining[*]information......
  • CF1353E K-periodic Garland 题解
    分析考虑DP。定义状态函数\(f_i\)表示处理完前\(i\)个字符且第\(i\)个字符为\(1\)时的最小代价。则对于\(i\),有两种情况:\(i\)不是第一个\(1\),则上一个\(1\)的位置必定为\(i-k\)。\(i\)是第一个\(1\),没有上一个\(1\)。得到转移方程:\(f_i=\min(f_{\max(......