问题标题: 酷町堂：3085 同余方程

Question

0

已解决

汪宇航

新手启示者

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

3 10

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

对于40%的数据，2 ≤b≤ 1,000；

对于60%的数据，2 ≤b≤ 50,000,000；

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

怎么做？

@谭迪元

汪宇航在2021-03-12 17:01:22追加了内容

@汪恺恒

@酷町猫

@张帆

汪宇航在2021-03-13 18:22:47追加了内容

d

Answer 1

已采纳

赵逸凡

初级启示者

因为本人目前还没上到数论，有比较优的思路：

考虑手推同余方程的单调性，如果有规律就三分法求最值

三分法：

while(l+eps<r) 
{
   double lmid=l+(r-l)/3;
   double rmid=r-(r-l)/3;
   if(f(lmid)<f(rmid)) 
       r=rmid;
   else    
       l=lmid;
}

因为这里是最小整数解，所以eps（单调三分精度）可以取1或者小数，如果是小数注意l的（floor|ceil）取整

然后看单调性选择f(lmid)<f(rmid)还是其他情况

枚举肯定超时，不用想的

Answer 2

汪宇航

新手启示者

顶

Answer 3

陈正朔

初级光能

这题要用到数论的知识（扩展欧几里得），一般枚举只能拿到60分