学步园

一个long a[N][N]二维数组，query(X1，Y1，X2，Y2)的意思是求以a[X1][Y1]为左下角，a[X2][Y2]为右上角的矩形里面所有元素的最大公约数，算法的空间复杂度不能大于a[N][N],时间复杂度尽量小，现有大量的输入X1，Y1，X2，Y2，求他们的最大公约数。给出两个函数名Inti(a[N][N]),query(X1，Y1，X2，Y2),让去写这两个函数的代码。

 

 

部分代码：

//分治法
Inti(a[N][N])
{
int x,y;
int a[N][N]=a[x][y];
x=x2-x1;y=y2-y1;
}

int cdiv(int a,int b)       //短除法求最大公约数
{
     if(a==b)
   return a;
  else if(a>b) return cdiv1(a-b,b); 
  else return cdiv1(b-a,a);
}

query(x1,x2,y1,y2)
{
if(x=0;y=1)
return cdiv(a[0][0],a[0][1]);
else
{
for(y1=0;y1<=y2;y2++){
for(x1=0;x1<=x2;x1++){
a[x1][y1]=cdiv(a[x1][y1],a[x1+1][y1]);
x1++;
}
y1++;
}
x=x/2;y=y/2;//每次缩小规模后，数组减半；
}

}

1、用分解质因数法，将几个数的所有公有质因数相乘的积；
2、用短除法。

 

#include<iostream>
using namespace std;
int cdiv1(int a,int b);   //求最大公约数
int cdiv2(int a,int b);    //求最大公约数
int cpow(int a,int b);      //求最小公倍数

int main()
{
 int a,b;
 cout<<"请输入a，b："<<endl;
 cin>>a>>b;
 cout<<"最大公约数是： "<<cdiv1(a,b)<<"\n";
 cout<<"最大公约数是： "<<cdiv2(a,b)<<"\n";
 cout<<"最小公倍数是： "<<cpow(a,b)<<endl;
 return 0;
}

int cdiv1(int a,int b)       //求最大公约数
{
     if(a==b)
   return a;
  else if(a>b) return cdiv1(a-b,b); 
  else return cdiv1(b-a,a);
}

int cpow(int a,int b)       //求最小公倍数
{
 int tem=cdiv1(a,b);
 return a*b/tem;
}

int cdiv2(int a,int b)          //求最大公约数
{
 int r;
 if(a<b) 
 {
  int temp=a;
  a=b;
  b=temp;
 }
 while(a%b)
 {
     r=a%b;
        a=b;
  b=r;
 }
    return  b;
}