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

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

穷举

我只有求 a*x + b*y = c 的代码
和你的 (k*x+b)%c = 0 其实是等价的，要不你自己改改

// ax + by = c (a!=0)
// x = x0 + n*k
bool gcd3( int a, int b, int c, int& x0, int& k )
{
    if( a == 0 )
        return false;

    int A=a, B=b, BX=0, BY=1;
    while( B )
    {
        BX = (a-B*BX)/A;
        BY = (b-B*BY)/A;
        int ta = A;
        A = B;
        B = ta%B;
    }
    if( c%A != 0 )
        return false;

    x0 = c*BY/(a*BY-b*BX);
    k = b/A;
    return true;
}

随手封装了一下，是否正确没测试
（最好还是重写）

#include <stdio.h>
#include <math.h>
#include <assert.h>

// ax + by = c (a!=0)
// x = x0 + n*k
_Bool gcd3( int a, int b, int c, int* x0, int* k )
{
    if( a == 0 )
        return 0;

    int A=a, B=b, BX=0, BY=1;
    while( B )
    {
        BX = (a-B*BX)/A;
        BY = (b-B*BY)/A;
        int ta = A;
        A = B;
        B = ta%B;
    }
    if( c%A != 0 )
        return 0;

    *x0 = c*BY/(a*BY-b*BX);
    *k = b/A;
    return 1;
}

// (k*x+b)%c=0 ---> k*x + -c*y = -b
_Bool NineTurnGalaxy( int k, int b, int c, int* px )
{
    int first, step;
    _Bool r = gcd3( k, -c, -b, &first, &step );
    if( !r )
        return r;

    *px = (first%step + abs(step))%step;
    return r;
}

int main( void )
{
    // (7*x+11)%17=0
    int x;
    _Bool r = NineTurnGalaxy( 7, 11, 17, &x );
    assert( r && (7*x+11)%17==0 );
}

学习了……

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

求两个整数的最大公约数所用的辗转相除法你应该知道吧，比如
24 78，依次变化为：
24  6
 0  6
所以最大公约数为6

求ax+by=c的整数解，本质也就是个辗转相除

现在以求 22*x + 54*y = 34 的整数解为例
先将最大的系数54分解成 2*22 + 10
即 22*x + 2*22*y + 10*y = 34
即 22*(1*x+2*y) + 10*y = 34

对比一下 22*x + 54*y = 34
和 22*(1*x+2*y) + 10*y = 34
可以看出第二项的系数下降了，同样的方法，继续让它下降下去

分解得 2*10*(1*x+2*y) + 2*(1*x+2*y) + 10*y = 34
合并得 10*(2*x+5*y) + 2*(1*x+2*y) = 34

再分解合并下去，最小的系数就是0了

一个系数是另一个系数的整数倍（那最大公约数就是最小的那个系数，都除以最小系数就变成了求 ax+y=c 的整数解，这个整数解一眼就可以看出是{x=0,y=c}、{x=1,y=c-a}、{x=2,y=c-2*a}、…… ）
那么可以看出 { 2*x+5*y=0，1*x+2*y=34/2 } 是一组整数解。
解上面的方程得 x=85, y=-34
将一开始的系数54，除以两个系数的最大公约数2，得到27
现在可以说 22*x + 54*y = 34 的整数解是 x = 85 + 27*k 等一系列的数

最后一个小问题就是怎么将 x = 85 + 27*k 中的85变成最小的一个非负整数？
这个简单，(first%step + abs(step))%step 就行，或者区分一下 第一个数为正为负，步长为正为负 四种情况分别写公式也行。

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

嗯,补充一下解(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编辑过]