NOIP2012 同余方程 题解
描写叙述
求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。
格式
输入格式
输入仅仅有一行,包括两个正整数a, b,用一个空格隔开。
输出格式
输出仅仅有一行,包括一个正整数x0。即最小正整数解。
输入数据保证一定有解。
限制
每一个測试点1s
提示
对于40%的数据,2 ≤b≤ 1,000;
对于60%的数据,2 ≤b≤ 50,000,000;
对于100%的数据,2 ≤a, b≤ 2,000,000,000。
分析:
解同余方程。比較水
欧几里德算法
program mod1;
var
a,b,x,y:longint;
procedure gcd(a,b:longint);
var t:longint;
begin
if b<>0
then gcd(b,a mod b)
else begin
x:=1;
y:=0;
exit;
end;
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
begin
readln(a,b);
gcd(a,b);
//writeln(x,' ',y);
writeln(((x mod b)+b)mod b);
end.
代码二:
program mod2;
procedure oujilide(a,b:int64;var d,x,y:int64);
begin
if b=0 then
begin
d:=a;
x:=1;
y:=0;
end
else
begin
oujilide(b,a mod b,d,y,x);
y:=y-x*(a div b);end;
end;
var
a,b,d,x,y:int64;
begin
assign(input,'mod.in');
reset(input);
assign(output,'mod.out');
rewrite(output);
readln(a,b);
oujilide(a,b,d,x,y);
while x<0 do
x:=x+b;
writeln(x);
close(input);
close(output);
end.
最新文章
- Javascript数据类型检测
- SQLServer(MSSQL)、MySQL、SQLite、Access相互迁移转换工具 DB2DB v1.1
- requirejs:性能优化-及早并行加载
- 华为上机:Tom的生日礼物
- 关于java对象的思考
- Redundant Call to Object.ToString()
- java日期处理总结(二)
- Python时间戳和日期
- Java中byte转int的方法
- remine chart2安装
- maven source
- git恢复误删除文件
- Nagios图像绘制插件PNP4Nagios部署和测试
- SQL语句的三大类
- ASP.NET Core MVC中的IActionFilter.OnActionExecuting方法,可以获取Controller的Action方法参数值
- 数据规整化:pandas 求合并数据集(交集并集等)
- Spring Boot:Caused by: org.apache.ibatis.binding.BindingException: Parameter &#39;deptId&#39; not found.
- c++builder 读写文件类
- 1030: [JSOI2007]文本生成器
- [转]优化Flash性能