专家
公告
财富商城
电子网
旗下网站
首页
问题库
专栏
标签库
话题
专家
NEW
门户
发布
提问题
发文章
pku2115（欧几里德算法，模线性方程）
2019-04-13 17:14
发布
生成海报
站内文章
/
模拟电子
13028
0
950
http://162.105.81.212/JudgeOnline/problem?id=2115
从题目可以推出 a+c*x = b (mod 2^k) => c*x = (b-a) (mod 2^k) 经典的模线性方程求解；可能会有出组解，第一个解就是最小解，注意解小于0的情况。
#include <iostream> using namespace std; __int64 extended_euclid(__int64 a,__int64 b,__int64 &x,__int64 &y){ __int64 ret; if(b == 0) { x = 1; y = 0; return a; } ret = extended_euclid(b,a%b,x,y); __int64 t = x; x = y; y = t - a / b * y; return ret; } __int64 modular_linear(__int64 a,__int64 b,__int64 n){ __int64 x,y; __int64 d = extended_euclid(a,n,x,y); if(b%d) return -1; __int64 e = x * (b / d) % n + n; return e % (n / d); } int main() { __int64 A,B,C,K; while(scanf("%lld %lld %lld %lld",&A,&B,&C,&K),A||B||C||K) { __int64 d=modular_linear(C,B-A,(__int64)1<<K); if(d==-1) printf("FOREVER/n"); else printf("%lld/n",d); } return 0; }
Ta的文章
更多
>>
Altium Designer 隐藏铺铜
0 个评论
电源与地之间接电容的原因分析
0 个评论
pku2115（欧几里德算法，模线性方程）
0 个评论
热门文章
×
关闭
举报内容
检举类型
检举内容
检举用户
检举原因
广告推广
恶意灌水
回答内容与提问无关
抄袭答案
其他
检举说明(必填)
提交
关闭
×
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 x0310 的文章《pku2115（欧几里德算法，模线性方程）》','https://www.xiaopingtou.net/article-53646.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}