Question

一道关于C语言的题，求教，求指点。谢谢！

问题是这样的：
两个正整数a,b最大公约数GCD（a,b），一般也被写成（a,b）,例如(1,2) = 1,(12,6)=6.
GCD很容易用欧几里得算法求得。 但是现在有一个新的问题：给定两个正整数N,M，问有多少个正整数X满足： 1<=X<=N,并且（X,N）>= M.
要求输入第一行为测试数据个数：T, T <= 3000;
接下来的T组测试数据，每组一行，每行两个正整数N和M（1 <= N <= 1000000000,1 <= M <= 1000000000）。
输出x的个数，占一行。
代码限制Memory Limit: 65536 kB
运行时间限制Time Limit: 1000 ms
我是这么写的：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a,b,n,m,x,f,g;//声明变量
scanf("%d",&a);//取次数
for(b=1;b<=a;b++)//数次数
{
g=0;
scanf("%d %d",&n,&m);//取数
for(x=m;x<=n;x++)//找一个介于MN之间的数
{
f=m;
for(;f<=x;f++)//找一个介于MX之间的数
{
if(x%f==0&&n%f==0);//判断是不是XN的公约数
{
g++;printf("%d %d\n",f,x);
f++;
break;
}
}
}
printf("%d\n",g);
}
return 0;
}

可是每次都时间超了。
希望哪个高手帮忙修改一下。

Answer 1

要提高效率，倒是可以~
不过挺麻烦
由于N值是确定的，那么M取值也很容易导出，比如N为6，那么M就只能取1，2，3，6（也就是可以整除N的素数，当然，1，6不是素数，也就是说除了本身和1以外，其它的取值都是素数）
当N,M值确定时，X的取值就是M*1,M*2,M*3(也就是M乘以素数的值），为保证M是最大公约数，这里的素数是不能整除(N/M)的。(1除外)也就是[1，N/M]区间的数素数的数量减去整除N/M的数量。
这样可以直接算出x的可取值个数，不用一个一个数的去检验。
不知道说明白了没~

追问

我想问代码应该怎样改？改成什么样子？

追答

#include
using namespace std;
int prime(int p[],int max)//建素数表
{
int i=3,j=0,k;
for(p[j]=2; ij)p[++j]=i;
}
return j+1;
}
int resdiv(int pr[],int na[],int n)//搜n的因子
{
int i,j=0;
for(i=0; n>1; i++)
{
if(n%pr[i]==0)
{
na[j++]=pr[i];
while(n%pr[i]==0 && n>1) n/=pr[i];
}
else if(pr[i]*pr[i]>n)
{
na[j++]=n;
break;
}
}
return j;
}
int gys(int a,int b)//最大公约数,辗转相除法
{
while(a>b?a%=b:b%=a);
return a>b?a:b;
}
int count;
int czz(int m,int n)
{
int j;
for(j=1; m*j=k && n%m==0)czz(m,n);
int i;
for(i=pos; i>T;
while(T--)
{
cin>>n>>m;
int len,x,j;
len=resdiv(pr,na,n);
count=0;
pzz(na,0,len,1,n,m);
cout<<count<<endl;
}
return 0;
}
…………不知能不能过，弄了半天~眼花了~代码都是拼凑出来的~

追问

麻烦再改改，还是没过。谢谢了！

追答

#include
using namespace std;
int prime(int p[],int max)//建素数表
{
int i=3,j=0,k;
for(p[j]=2; ij)p[++j]=i;
}
return j+1;
}
int resdiv(int pr[],int na[],int n)//搜n的因子
{
int i,j=0;
for(i=0; n>1; i++)
{
if(n%pr[i]==0)
{
na[j++]=pr[i];
while(n%pr[i]==0 && n>1) n/=pr[i];
}
else if(pr[i]*pr[i]>n)
{
na[j++]=n;
break;
}
}
return j;
}
/***
int gys(int a,int b)//最大公约数,辗转相除法
{
while(a>b?a%=b:b%=a);
return a>b?a:b;
}
***/
int count;
int czz(int pr[],int m,int n)
{
int i,j,len,cp[32];
len=resdiv(pr,cp,n/m);
for(j=1; m*j=k)czz(pr,m,n);
int i;
for(i=pos; i>T;
while(T--)
{
cin>>n>>m;

int len,x,j;
len=resdiv(pr,na,n);
count=0;
pzz(pr,na,0,len,1,n,m);
cout<<count<<endl;
}
return 0;
}
小改了下，效率提高一点~

Answer 2

//可以用欧几里德算法直接求出(x,n)，然后和m比较,效率明显提高，但还远未达到1000ms的要求，n还不到1千万就超时了 （q9550 cpu)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
clock_t s;
int a,b,n,m,x,f,g;
int n1,x1;
scanf("%d",&a);
for(b=1;b<=a;b++)
{
g=0;
scanf("%d %d",&n,&m);
s=clock();
for(x=m;x<=n;x++)
{
x1=x;n1=n;
while(1)
{
n1=n1%x1;
if(n1==0)
{
f=x1;
break;
}
x1=x1%n1;
if(x1==0)
{
f=n1;
break;
}
}
if(f>=m)
{
//printf("%d %d ",x,f);
g++;
}

}
s=clock()-s;
printf("%d %dms\n",g,s);

}

return 0;
}

1
8888888 56
39096 1326ms
请按任意键继续. . .

release版本稍微快点，没有本质改变
1
8888888
56
39096 1107ms
请按任意键继续. . .

追问

所以呢，麻烦再帮忙改改。谢谢！

追答

没数学模型是不行的，我们现在的算法还是暴力型的，时间复杂度是O(n^2)级别的
至少要O(n)的算法才可能满足10亿以内计算时间小于1000ms的要求
要是这是个试题的话，我猜有O(1)的算法