| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 197 人关注过本帖
标题:求一个关于(k*x+b)%c=0的快速算法~
只看楼主 收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3654
专家分:10447
注 册:2016-10-22
结帖率:100%
  已结贴   问题点数:20  回复次数:8   
求一个关于(k*x+b)%c=0的快速算法~
如题~就是求一个(k*x+b)%c=0的快速算法~其中k和b是一个在用户端输入的1e5以内的整型实数,求x的最小值~
注意效率要尽可能高的~

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

2017-10-12 01:03
wp231957
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:神界
等 级:版主
威 望:363
帖 子:12336
专家分:48787
注 册:2012-10-18
  得分:1 
穷举

DO IT YOURSELF !
2017-10-12 08:58
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:211
帖 子:5066
专家分:27846
注 册:2011-1-18
  得分:6 
我只有求 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;
}
2017-10-12 09:08
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:211
帖 子:5066
专家分:27846
注 册:2011-1-18
  得分:6 
随手封装了一下,是否正确没测试
(最好还是重写)

程序代码:
#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 );
}

2017-10-12 09:24
小青345
Rank: 1
等 级:新手上路
帖 子:38
专家分:1
注 册:2017-8-24
  得分:1 

买房租房上爱心房产网
2017-10-12 10:51
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3654
专家分:10447
注 册:2016-10-22
  得分:0 
回复 4楼 rjsp
学习了……

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

[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
2017-10-12 13:52
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:211
帖 子:5066
专家分:27846
注 册:2011-1-18
  得分:6 
回复 6楼 九转星河
求两个整数的最大公约数所用的辗转相除法你应该知道吧,比如
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 就行,或者区分一下 第一个数为正为负,步长为正为负 四种情况分别写公式也行。
2017-10-12 15:45
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3654
专家分:10447
注 册:2016-10-22
  得分:0 
回复 7楼 rjsp
说得好~就是辗转相除法思想把系数逐渐降低~可以理解~

[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
2017-10-12 16:22
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3654
专家分:10447
注 册:2016-10-22
  得分:0 
嗯,补充一下解(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编辑过]


[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
7 天前 04:32







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.074220 second(s), 8 queries.
Copyright©2004-2017, BCCN.NET, All Rights Reserved