poj2115clooooops[一元线性同余方程]

关键词：

一元线性同余方程

定义：

$a$，$b$是整数，$m$是正整数，形如

　　　　　　　　　　　　　　　　　　　　　　　　　　　　$axequiv b,(mod, m)$

且$x$是未知数的同余式称作一元线性同余方程。

对于方程$axequiv b,(mod, m)$， 可以把它写成二元一次不定式$ax+my=b$。要想方程有解，必须满足$(a,m)mid d$。 这时利用扩展欧几里得求出$ax+my=(a,m)$

的一个特解，在乘上$b/(a,m)$就是我们所要的一个特解。

利用公式：

$ax_0+my_0=d=ax+myRightarrow a(x-x_0)+m(y-y_0)=0$

$(frac{a}{(a,m)}, frac{m}{(a,m)}) = 1 $

$x = x_0-frac{m}{(a,m)}t$

 

这样就得到了$x$的所有解，其中最小的整数解是$ (x,mod,frac{m}{(a,m)}+frac{m}{(a,m)} ) ,mod,frac{m}{(a,m)} $

POJ 2115 就是求当$a=C$，$b=B-A$，$m=2^k$的最小解

 

 

 

poj2115clooooops（模线性方程）

http://poj.org/problem?id=2115题意：给你一个变量，变量初始值a，终止值b，每循环一遍加c，问一共循环几遍终止，结果mod2^k.如果无法终止则输出FOREVER。思路：根据题意原题可化成c*x=b-amod(2^k)，然后解这个模线性方程。1#include<iostre... 查看详情

poj1061-青蛙的约会-[exgcd求解一元线性同余方程]

...考exgcd：http://www.cnblogs.com/dilthey/p/6804137.html） 定理2：一元线性同余方程ax≡n(modb)有解，当且仅当gcd(a,b)|n.也就是说，解出了ax+by=gcd(a,b)，就相当于解出了ax≡n(modb) 查看详情

poj2115单变元模线性方程

链接：http://poj.org/problem?id=2115题意：给出a,b,c,k，问从a开始每次+c，加多少次能变成b，结果模2^k题解：计算cx同余(b-a)(mod2^k)即可代码：31llextgcd(lla,llb,ll&x,ll&y){32lld=a;33if(b){34d=extgcd(b,a%b,y,x);35y-=(a/b)*x;36}37elsex=1, 查看详情

poj2115clooooops(exgcd)(代码片段)

poj2115CLooooops题意：对于C的for(i=A;i!=B;i+=C)循环语句，问在k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出死循环。（k位==mod$2^k$）列出方程：$A+CxequivB(modequad2^k)$转换一下：$Cx+ky=B-A$用exgcd解出$Cx+k... 查看详情

hdu1573x问题一元线性同余方程组

...路：先求出数组b[]中全部数的最小公倍数lcm，再求解出该一元线性同余方程组在 查看详情

poj2115clooooops

https://cn.vjudge.net/problem/POJ-2115题目ACompilerMystery:WearegivenaC-languagestyleforloopoftypefor(variable=A;variable!=B;variable+=C)statement;I.e.,aloopwhichstartsbysettingvariabletovalueAandwhilev 查看详情

poj2115clooooops

DescriptionACompilerMystery:WearegivenaC-languagestyleforloopoftype for(variable=A;variable!=B;variable+=C)statement;I.e.,aloopwhichstartsbysettingvariabletovalueAandwhilevariableisnotequaltoB,re 查看详情

数论线性同余方程的应用poj2891

StrangeWaytoExpressIntegersTimeLimit: 1000MS MemoryLimit: 131072KTotalSubmissions: 17321 Accepted: 5828Description ElinaisreadingabookwrittenbyRujiaLiu,whichintroduc 查看详情

poj2115clooooops

CLooooopsTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 28251 Accepted: 8079DescriptionACompilerMystery:WearegivenaC-languagestyleforloopoftype for(variable= 查看详情

poj2115：clooooops

CLooooopsTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 19536 Accepted: 5204DescriptionACompilerMystery:WearegivenaC-languagestyleforloopoftype for(variable= 查看详情

poj2891strangewaytoexpressintegers(线性同余方程组)

ElinaisreadingabookwrittenbyRujiaLiu,whichintroducesastrangewaytoexpressnon-negativeintegers.Thewayisdescribedasfollowing: Choose k differentpositiveintegers a1, a2, &hel 查看详情

poj2115clooooops

1/*2POJ2115CLooooops3http://poj.org/problem?id=21154扩展欧几里得5题意：求x,s.t.(a+c*x)=b(mod1<<k)6<=>c*x=b-a(mod1<<k)7*/8#include<cstdio>9#include<algorithm>10#include<cstring&g 查看详情

nefu84-五指山-[exgcd求解一元线性同余方程]

题目链接：http://acm.nefu.edu.cn/JudgeOnline/problemShow.php?problem_id=84TimeLimit:1000ms　　MemoryLimit:65536KDescription西游记中孙吾空大闹天宫，如来佛祖前来降伏他，说道：“我与你打个赌赛；你若有本事，一筋斗打出我这右手掌中，算你赢，... 查看详情

poj2115clooooops（exgcd）

 【题目链接】 http://poj.org/problem?id=2115 【题目大意】　　求for(variable=A;variable!=B;variable+=C)的循环次数，　　其中变量为k比特无符号整数。 【题解】　　题目等价于求解Cx=(B–A)(mod2^k)，利用扩展欧几里得算法可... 查看详情

poj2115clooooops

思路：求最小的非负整数t使得C*t%2k=(B-A) %2k。 实现：1#include<iostream>2#include<cstdio>34usingnamespacestd;5typedeflonglongll;67llabs(llx)8{9returnx<0?-x:x;10}1112llextgcd(lla,llb,ll&x,ll 查看详情

poj-2115clooooops扩展欧几里得（做的少了无法一眼看出）

题目大意&&分析：for(variable=A;variable!=B;variable+=C)statement;这个循环式子表示a+c*n（n为整数）==b是停止循环，题目中要求（a+c*n）%2^k=b时停止循环；所以我们可以得到一个形如ax+by=c的方程式：a+c*n=b+2^k*m；通过移项：c*x-2^k*m=b-a... 查看详情

poj2115--clooooops--扩展欧几里得

Description我们知道c中有这样一个循环语句for(inti=A;i<=B;i+=C){　　i%=(1<<k);}给定A,B,C,k的值，问此循环是否能够在有限次数内终止，不能则输出"FOREVER"。 SampleInput33216372167321634216000 0SampleOutput0232766FOREVER题解：这题和poj1067 查看详情

clooooops（poj2115）

大致题意：对于C的for(i=A;i!=B;i+=C)循环语句，问在k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数。否则输出死循环。 解题思路：题意不难理解，只是利用了k位存储系统的数据特性进行循环。例如int型... 查看详情