论坛 › 【编程】编程圣殿 › [数学题]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以后不要步我后尘啊！！！
#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;

        }
}

查看完整版本: [数学题]zju_1577