如题~就是求一个(k*x+b)%c=0的快速算法~其中k和b是一个在用户端输入的1e5以内的整型实数,求x的最小值~
注意效率要尽可能高的~

[此贴子已经被作者于2017-10-12 01:05编辑过]

学习了……

刚刚搜了关于不定方程ax+by=c的整数解……我倒也没想到这个和不定方程有点联系~
就是要这种效率……这个算法我要慢慢消化一下~

说得好~就是辗转相除法思想把系数逐渐降低~可以理解~

嗯,补充一下解(k*x)%b=c的口算过程~

以(7*x)%17=11为例~

用辗转相除法思想记录前相继两个余数的步长~
余数为7的步长为1~
7*3-17=4;
可见余数为4的步长为3;
4*2-7=1;
可见余数为1的步长为3*2-1=5;

至此容易知道11的步长为5*11=55;
周期为17,所以最小正整数解为55-17*3=4;

验证得(7*4)%17=11;

或者可以再来个大一点的~

例如计算(31*x)%75=19;

已知条件得余数为31的步长为1;
31*3-75=18;
求得余数为18的步长为3;
18*2-31=5;
求得余数为5的步长为2*3-1=5;
5*4-18=2;
求得余数为2的步长为5*4-3=17;
2*3-5=1;
求得余数为1的步长为17*3-5=46;
容易得余数19的步长为46*19;
由周期为75得结果为(46*19)%75=49;
~

[此贴子已经被作者于2017-10-13 04:45编辑过]