工大后院

标题: [数学题]zju_1577 [打印本页]

作者: sheep426 时间: 2005-7-23 12:50
标题: [数学题]zju_1577
http://acm.zju.edu.cn/show_problem.php?pid=1577
GCD & LCM
Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 5655 Accepted Submit: 1520
Given x and y(2 <= x <= 100,000, 2 <= y <= 1,000,000), you are to count the number of p and q such that:
1) p and q are positive integers;
2) GCD(p, q) = x;
3) LCM(p, q) = y.
Input
x and y, one line for each test.
Output
Number of pairs of p and q.
Sample Input
3 60
Sample Output
4
Author: ZHOU, Qiang
Submit Back Status
Zhejiang University Online Judge V1.0

[ Last edited by sheep426 on 2005-7-23 at 12:59 ]

作者: sheep426 时间: 2005-7-23 12:53
我的代码，由于还是模拟，所以很慢，有很大的优化空间
Accepted 1577 C++ 00:00.67 920K sheep

#include <iostream>
#include <cmath>

using namespace std;
bool isprime(long i,long j)
{
if(i==1 || j==1 )
return true;
for(int t=2;t<=i;t++)
if(i%t==0 && j%t==0)
return false;
return true;

}

int main()
{
long x,y,count,p,q,k;
while(cin >>x >> y)
{
count = 0;
if(y%x)
{
cout<<0<<endl;
continue;
}
else if (y == x)
{
cout<<1<<endl;
continue;
}
else
{
long i;
k = y /x;
for(i = 1;i<=k;i++)
{
if(k % i == 0)
{
if(isprime(k/i,i) )
count++;
}
}
}
cout << count<<endl;

}
}

作者: 剑乱 时间: 2005-7-23 13:02
1330875 2005-07-23 12:32:49 Accepted 1577 C++ 00:00.01 380K JayShao
开始的时候思维不够周密，找了很久才发现当X=Y的时候一定会是1，只把精力放在一般的情况上，而特殊的地方没注意到。希望各位ACMer以后不要步我后尘啊！！！
[code][code]#include<stdio.h>
int x,y;
int check(int a,int b)
{ int t,t2;
t2=a*b;
while(a%=b)
  { t=a;a=b;b=t;

  }
  t2/=b;
if(x==b&&y==t2)return 1;
else return 0;

}

int main()
{ int i,sum,product,t3;
  while(scanf(\"%d %d\",&x,&y)!=EOF)
  {
if(x==y)printf(\"1\\n\");
else
{

   sum=0;
   product=x*y;
   for(i=x;i<=product;i=i+x)
   { t3=product/i;
      if(i>t3)break;
      if(!(t3%x)){if(check(i,t3))sum++;}

   }
   printf(\"%d\\n\",2*sum);

}

  }
return 0;
}

[ Last edited by 剑乱 on 2005-7-23 at 13:06 ]

作者: sheep426 时间: 2005-7-23 13:15
这样不好点吗？
#include<stdio.h>
int x,y;
int check(int a,int b)
{
int t,t2;
t2=a*b;
while(a%=b)
{
t=a;
a=b;
b=t;
}
t2/=b;
if(x==b&&y==t2)
return 1;
else
return 0;

}

int main()
{
int i,sum,product,t3;
while(scanf(\"%d %d\",&x,&y)!=EOF)
{
sum=0;
product=x*y;
for(i=x;i<product;i=i+x)
{
t3=product/i;
if(i>t3)
break;
if(!(t3%x))
{
if(check(i,t3))
sum++;
}

   }
printf(\"%d\\n\",2*sum);
}
   return 0;
}

作者: sheep426 时间: 2005-7-23 13:35
优化一下，好了点，算不想了
Accepted 1577 C++ 00:00.40 920K sheep

#include <iostream>
#include <cmath>

using namespace std;
int gcd(int a,int b)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}

int main()
{
int x,y,count,p,q,k;
while(cin >>x >> y)
{
count = 0;
if(y%x)
{
cout<<0<<endl;
continue;
}
else if (y == x)
{
cout<<1<<endl;
continue;
}
else
{
long i;
k = y /x;
for(i = 1;i<=k;i++)
{
if(k % i == 0)
{
if(gcd(x*k/i,x*i) == x )
count++;
}
}
}
cout << count<<endl;

}
}

欢迎光临工大后院 (https://www.gdutbbs.com/)