精华内容
下载资源
问答
  • gcd

    千次阅读 2019-07-16 19:09:08
    gcd gcd(a,b)=gcd(b,a mod b) 边界条件:gcd(a,0)=a gcd(a,b) * lcm(a,b)=a*b 于是求lcm: a/gcd(a,b)*b; 先除保证中间结果不会溢出 //递归写法 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } //求a%b余数 ...

    gcd

    gcd(a,b)=gcd(b,a mod b)
    边界条件:gcd(a,0)=a

    gcd(a,b) * lcm(a,b)=a*b

    于是求lcm:
    a/gcd(a,b)*b;
    先除保证中间结果不会溢出

    //递归写法
    int gcd(int a,int b)
    {
    	return b==0?a:gcd(b,a%b);
    }
    
    //求a%b余数
    int gcd(int a, int b)
    {
    	int r;
    	while (b > 0)//(a%b的余数给b, b给a,最后b==0的a就是最终值)
    	{
    		r = a % b;
    		a = b;
    		b = r;
    	}
    	return a;
    }
    

    //这里的递归不会栈溢出
    //gcd函数的递归层数不超过4.785lgN+1.6723
    N=max(a,b);
    让gcd递归最多的是gcd(Fn, F(n-1)), Fn是Fibonacci数

    拓展欧几里得算法的板子

    //gcd的同,求出ax+by=gcd(a,b)的一个解
    __int64 extend_gcd(__int64 a, __int64 b, __int64& x, __int64& y)
    {
    	if (a == 0 && b == 0) return -1;//无最大公约数
    	if (b == 0) { x = 1; y = 0; return a; }
    	__int64 d = extend_gcd(b, a % b, y, x);
    	y -= a / b * x;
    	return d;//得到a b的最大公因数
    }
    
    展开全文
  • GCD

    2020-01-27 17:57:22
    ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); } 二进制算法 在1e4以内的运算次数中,gcd的递归比较快,但是当运算次数高达1e6及以上,位运算算法非常节省时间 实现原理: 若a、b都是偶数,则gcd(a,b...

    辗转相除法(欧几里得算法)

    时间复杂度O(logn)O(logn)

    //不必在意a、b大小关系,即使a小于b,第一次递归也会交换a和b
    typedef long long ll;
    ll gcd(ll a,ll b){
    	return b==0?a:gcd(b,a%b);
    }
    
    

    二进制算法

    在1e4以内的运算次数中,gcd的递归比较快,但是当运算次数高达1e61e^6及以上,位运算算法非常节省时间

    实现原理:

    a,ba,b都是偶数,则gcd(a,b)=2gcd(a/2,b/2)gcd(a,b)=2*gcd(a/2,b/2)

    a,ba,b都是奇数,则有gcd(a,b)=gcd(ab,b)gcd(a,b)=gcd(a-b,b)

    aa为偶数,bb为奇数,则有gcd(a,b)=gcd(a/2,b)gcd(a,b)=gcd(a/2,b)

    int gcd(int a,int b){
    	int c=1;
    	while(a-b){
    		if(a&1){
    			if(b&1){
    				if(a>b)a=(a-b)>>1;
    				else b=(b-a)>>1;
    			}else b>>=1;
    		}else{
    			if(b&1)a>>=1;else c<<=1,a>>=1,b>>=1;
    		}
    	}
    	return c*a;
    }
    

    递推求gcd

    n,mn,m以内任意两数的gcd,lcmgcd,lcm,时间复杂度O(nm)O(nm)

    类似埃氏筛法,因为前面的数互质,他们两两之间最大公因数都是确定为11的,如"1 1",“1 2”,“2 3”,“3 4”。从小到大枚举kk,这样kikikjkj的最大公因数就是k,同理最小公倍数就是(kikj)/k=ijk(ki*kj)/k=i*j*k

    int gcd[maxn][maxn],lcm[maxn][maxn];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if(!gcd[i][j])
            for(int k=1;k*i<=n && k*j<=m;k++)
                gcd[k*i][k*j]=k,lcm[k*i][k*j]=i*j*k;
    

    GCD常见推导

    • gcd(a,b)=c>gcd(a/c,b/c)=1gcd(a,b)=c -----> gcd(a/c,b/c)=1
    • lcm(a,b)=ab/gcd(a,b)=c>cgcd(a,b)=ab>gcd(a,b)=ab/clcm(a,b)=a*b/gcd(a,b)=c ------> c*gcd(a,b)=a*b ------> gcd(a,b)=a*b/c
    • gcd(a,b,c)=gcd(gcd(a,b),c)gcd(a,b,c)=gcd(gcd(a,b),c)gcdgcd具有区间可加性,当我们对一个区间求gcdgcd时可以先求出所有的任何小区间的gcdgcd再逐层求出大区间的gcdgcd,可以考虑线段树或者dpdp

    GCD常见应用

    如下图n×mn×m的方格棋盘,从左下角到右上角穿过一条直线,求直线和多少个方格内部有交点
    在这里插入图片描述
    观察每一个点,不难发现每当和一条纵线相交后,下一次一定个横线相交,不考虑特殊点的情况下是n+mn+m。但是像图中加粗的点那样,就重复计算了一次,因此需要找出这种特殊点的个数。从左下角开始找第一个特殊点,其左下角为2×32×3的矩形;然后找第二个特殊点,左下角为4×64×6的矩形;第三个为6×96×9的矩形…我们发现一个共同点,就是这些矩形都和n×mn×m的矩形相似,所以特殊点的个数也就是gcd(n,m)gcd(n,m),故答案就是n+mgcd(n,m)n+m-gcd(n,m)

    2.有一个n×nn×n的方阵,给出方阵中的两个坐标(x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2),如何判断两点的连线不会和其他点相交
    在这里插入图片描述
    如图所示,显然如果两个点之间会有交点,那么ABC△ABCAEF△AEF会构成相似三角形,和第一个例子类似,那么就出现gcd(BC,AC)>1gcd(|BC|,|AC|)>1

    因此令a=abs(x1x2),b=abs(y1y2)a=abs(x_1-x_2),b=abs(y_1-y_2),当且仅当gcd(a,b)=1gcd(a,b)=1时两点的连线才不会和其他点相交

    GCD和LCM在质因数分解下的意义

    假设aa经过质因数分解后为P1k1P2k2,...PnknP_1^{k_1}*P_2^{k_2},...*P_n^{k_n},b经过质因数分解为Q1t1Q2t2,...QmtmQ_1{t_1}*Q_2^{t_2},...*Q_m^{t_m}

    假设质因子ppaabb共有的质因子,在aapp的幂次为k1k_1,在bbpp的幂次为k2k_2,又因为所有的质因子两两互质,互不影响

    那么gcd(a,b)gcd(a,b)的质因子pp实际上的幂次为min(k1,k2)min( k_1,k_2 )lcm(a,b)lcm(a,b)的质因子pp实际上的幂次为max(k1,k2)max( k_1,k_2 )

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,865
精华内容 19,146
关键字:

gcd