题目名称 1265. [NOIP 2012]同余方程
输入输出 mod.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatar王者自由 于2012-11-11加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:617, 提交:1159, 通过率:53.24%
Gravatar_Itachi 100 0.000 s 0.00 MiB C++
Gravatar金身人面兽 100 0.000 s 0.00 MiB C++
Gravatardestiny 100 0.000 s 0.00 MiB C++
GravatarRespawn 100 0.000 s 0.00 MiB C++
GravatarHzoi_Yniverse 100 0.000 s 0.00 MiB C++
Gravatar可以的. 100 0.000 s 0.00 MiB C++
Gravatar用ۣۣۣۣۣۣۣۣۣۣۣۣۣۣۣ 100 0.000 s 0.00 MiB C++
Gravatar‎MistyEye 100 0.000 s 0.00 MiB C++
Gravatar派特三石 100 0.000 s 0.00 MiB C++
Gravatar可以的. 100 0.000 s 0.00 MiB C++
本题关联比赛
NOIP 2012 Day2
NOIP 2012 Day2
20160303
防止浮躁的小练习v0.6
防止浮躁的小练习v0.6
201712练习
关于 同余方程 的近10条评论(全部评论)
回复 @据说这是zzy : 多谢指点!
Gravatar夜莺
2019-11-06 22:39 26楼
总算会了这个东西,2018,预祝自己和大家rp++
GravatarHale
2018-10-27 21:03 25楼
本题需要的知识
欧几里得
百度百科
扩展欧几里得
http://blog.csdn.net/zhjchengfeng5/article/details/7786595
裴蜀定理
百度百科
还有你还需要个 chh
给你讲讲
谢 大哥
Gravatar据说这是zzy
2017-10-26 00:29 24楼
啦啦啦..............
---------------
2017.9.21
复习EX_GCD
GravatarJustWB
2017-09-21 13:26 23楼
看来我的快读快写写的有问题。。。
GravatarHyoi_0Koto
2017-07-16 16:32 22楼
GravatarAntiLeaf
2017-05-25 15:59 21楼
回复 @QhelDIV :
如果早一点看评论,就不会傻傻的以为暴力可以过。。。
Gravatarfate1
2017-03-10 19:39 20楼
int 40 longlong 60 欧鸡 100
GravatarAys
2016-11-17 13:06 19楼
终于学会了拓展欧几里德的正确写法= =
GravatarAntiLeaf
2016-10-12 07:49 18楼
直接extgcd就过了……
GravatarBillAlen
2016-09-22 20:25 17楼

1265. [NOIP 2012]同余方程

★☆   输入文件:mod.in   输出文件:mod.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

求关于 $x$ 的同余方程 $ax\equiv1(\mod b)$ 的最小正整数解。

【输入格式】

输入只有一行,包含两个正整数 $a,b$,用一个空格隔开。

【输出格式】

输出只有一行,包含一个正整数 $x_0$,即最小正整数解。输入数据保证一定有解。

【样例输入】

3 10

【样例输出】

7

【数据范围】

对于 40% 的数据,$2≤b≤1,000$; 

对于 60% 的数据,$2≤b≤50,000,000$; 

对于 100% 的数据,$2≤a,b≤2,000,000,000$。