程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 歐幾裡得算法&&擴展歐幾裡得算法

歐幾裡得算法&&擴展歐幾裡得算法

編輯:C++入門知識

歐幾裡得算法:gcd(a,b)=gcd(b,a%b);證明略
擴展歐幾裡得算法:y-=a/b*x;
應用判斷不定方程是否有整數解,求不定方程的整數解,判斷在規定范圍內有多少整數解.
[cpp]
#include<iostream> 
#include<string.h> 
using namespace std; 
int a,b,x,y,d; 
/*void gcd(int a,int b )
{
    if(!b){x=1;y=0;d=a;}
    else 
    {
        gcd(b,a%b);
        int temp=x;
        x=y;
        y=temp-a/b*x;
 
    }
}*/ 
void gcd(int a,int b,int &d,int &x,int &y) 

    if(!b) x=1,y=0,d=a; 
    else gcd(b,a%b,d,y,x),y-=a/b*x; 
     

int main() 
{    www.2cto.com
    int T; 
    scanf("%d",&T); 
    while(T--) 
    { 
        int a,b; 
        scanf("%d%d",&a,&b); 
        gcd(a,b,d,x,y); 
        printf("%d*%d+%d*%d=%d\n",a,x,b,y,d); 
    }return 0; 
 

作者:smallacmer

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved