首页 > 其他分享 >P5656 【模版】二元一次不定方程(exgcd)

P5656 【模版】二元一次不定方程(exgcd)

时间:2024-03-19 18:22:31浏览次数:30  
标签:max gcd dfrac 方程 exgcd 模版 P5656 ax

综合考查 exgcd 功力的题目。

没有整数解当且仅当 \(\gcd(a,b)\nmid c\),直接输出 -1

用 exgcd 解方程 \(ax+by=\gcd(a,b)\) 得到一组特解 \(x_0,y_0\)。对原方程变形得到 \(a\cdot\dfrac{xc}{\gcd(a,b)}+b\cdot\dfrac{yc}{\gcd(a,b)}=c\),于是有 \(ax+by=c\) 的一组特解 \(x_1=\dfrac{xc}{\gcd(a,b)},y_1=\dfrac{yc}{\gcd(a,b)}\)。

接下来,由「同余方程」一题中的技巧,用 x=(x%b+b)%b, y=(y%a+a)%a; 求出 \(x,y\) 的最小取值 \(x_{\min},y_{\min}\),因为 \(x\) 增大 \(y\) 减小,可以直接分别带入原方程,求出 \(y_{\max},x_{\max}\)。如果 \(x_{\max},y_{\max}<0\),则没有正整数解,直接输出两个最小值即可;否则有正整数解,分别输出最大值、最小值和解的个数。

标签:max,gcd,dfrac,方程,exgcd,模版,P5656,ax
From: https://www.cnblogs.com/th19/p/17920758.html

相关文章

  • WPF —— 控件模版和数据模版
    1:控件模版简介:自定义控件模版:自己添加的样式、标签,控件模版也是属于资源的一种,    每一个控件模版都有一唯一的key,在控件上通过template属性进行绑定什么场景下使用自定义控件模版,当项目里面多个地方使用到相同效果,这时候可以把相同    效果封装成一个......
  • GPT实战系列-LangChain的Prompt提示模版构建
    GPT实战系列-LangChain的Prompt提示模版构建LangChainGPT实战系列-LangChain如何构建基通义千问的多工具链GPT实战系列-构建多参数的自定义LangChain工具GPT实战系列-通过Basetool构建自定义LangChain工具方法GPT实战系列-一种构建LangChain自定义Tool工具的简单方法G......
  • 一种奇怪的方式(.gitignore模版问题)导致部署在CentOS服务器上采用Nginx和uWSGI的Django
    如图所示,在本地测试时好好的页面部署在CentOS服务器上用了Nginx和uWSGI就显示不了CSS样式。并且控制台上显示这一部分样式404Notfund于是我就开始各种查找技术贴学习,有说权限没开要修改nginx.conf配置中usernginx;为userroot;的,有说location结尾要加/的,有说DEBUG=True的,有说要......
  • 模版匹配——inspect_shape_model
    inspect_shape_modelcreatesarepresentationofashapemodel.TheoperatorisparticularlyusefulinordertodeterminetheparametersNumLevelsandContrast,whichareusedincreate_shape_model,create_scaled_shape_model,orcreate_aniso_shape_model,q......
  • 微信小程序(九)模版样式
         ......
  • 模版匹配——set_shape_model_param
    1.'min_contrast'最小对比度SetstheminimumcontrastoftheobjectinthesearchimagesfortheshapemodelModelID.Thereby,thevalueof'min_contrast'thatwasoriginallyset,e.g.withcreate_shape_model,isoverwrittenfortheshape......
  • 代码模版
    功能实现代码拦截器拦截器逻辑@ComponentpublicclassLoginInterceptorimplementsHandlerInterceptor{@AutowiredprivateRedisTemplateredisTemplate;@OverridepublicbooleanpreHandle(HttpServletRequestrequest,HttpServletResponserespon......
  • EMR 电子病历模版分类树
    EMR 病案首页 病案首页 病案首页(中医) 住院志 入院记录(通用) 入院记录(儿科) 入院记录(妇科) 出院记录(通用) 出院记录(儿科) 出院记录(妇科) 24小时内入出院记录 24小时内入院死亡记录 入院记录(神经内科) 病程记录 首次病程记录 日常病程记录 抢救记录 输血记录 有创诊疗操作......
  • pp_orange 的新poly模版
    点击查看代码namespacePoly{int*r[23];intrr[MAX<<1];structpolyinit{ polyinit(){ intnw=1; intlen=1; while(nw+len<=(MAX<<1)){ intpos=lg(len); r[pos]=rr+nw; rep(i,1,len)r[pos][i]=(r[pos][i>>1]>>1)|((i&a......
  • 模版
    任务详情:自学教材第1,2章,提交学习笔记Part1知识点归纳&GPT提问知识点归纳木桶原理每个安全系统的安全性都取决于它最脆弱的环节攻击者通过建立攻击树讨论对多个环节的攻击方法强化最脆弱环节,对多个环节进行强化使系统具备纵深防御的性质对手设定我们的任务是构建一个能够......