193 条题解

  • 5
    @ 2019-05-27 12:09:17
    #include<iostream>
    #include<cmath>
    using namespace std;
    int m,n,ans;
    int gcd(int x,int y)
    {
        if(y==0)    {return x;}
        return gcd(y,x%y);
    }
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=sqrt(m*n);i++)
        {
            if((n*m)%i==0&&gcd(i,(n*m)/i)==n)  ans++;
        }
        cout<<ans*2;
        return 0;
    }
    
  • 2
    @ 2019-09-24 13:25:47

    大概不是最优解...
    思路:y/x必为两个互质的数,问原因自己翻数论书去

    #include <iostream>
    #include <math.h>
    using namespace std;
    int gcd(long a,long b){ return b==0?a:gcd(b,a%b); }
    int main()
    {
        long x,y;
        cin>>x;
        cin>>y;
        long num=y/x;
        long hits=0;
        if(y%x!=0){
            cout<<0;
            return 0;
        }
        for(long i=1;i<=num;i++){
            if(num%i!=0)continue;
            if(gcd(i,num/i)!=1)continue;
            ++hits;
        }
        cout<<hits;
    }
    
  • 1
    @ 2018-08-12 10:24:21

    这是一道较为简单的数论题
    首先我们拿到这个题可以写个暴力找一下规律,我们会发现答案要么是0要么是2的幂次方,这个时候我们可以想办法去找这个幂次方

    下面开始正题
    根据唯一分解定理可知,任何一个数的分解质因数都只有一种方法
    同时,关于LCM和GCD的性质,我们可以得知,对于某个素因子ai,其在GCD中出现的次数等于在x,y中出现次数较少的,在LCM中出现的次数等于在x,y中出现次数较多的
    这样的话我们的分解方法就已经固定了,每出现一个素因子bi,假如它在x,y中出现的次数不相同,答案就要乘上2,同时,如果分解过程中GCD的某个素因子数大于LCM中的素因子数,说明答案不存在,此时输出0
    数据较小,没有必要筛素数,硬做即可

    #include<iostream>
    using namespace std;
    int p1[1000010],p2[1000010];
    int main()
    {
        int x,y,i,j,num=0,ans=1,x1,y1;
        cin>>x>>y;
        x1=x;
        y1=y;
        if(x>y)
        {
            cout<<0;
            return 0;
        }
        for(i=2;i<=x;i++)
         {
            if(x%i==0)
             {
                p1[i]++;
                x/=i;
                i--;
             }
         }
         for(i=2;i<=y;i++)
         {
            if(y%i==0)
            {
                p2[i]++;
                y/=i;
                i--;
            }
         }
         for(i=2;i<=y1;i++)
         {
            if(p1[i]!=p2[i])
             ans*=2;
            if(p1[i]>p2[i])
            {
                ans=0;
                break;
            }
         }
         cout<<ans;
         return 0;
    }
    
  • 1
    @ 2018-07-13 16:38:44

    本质是分解质因数,求得质因数的数量n(相同的公因数只算1次),最后结果为2^n

    PS:前面也考虑过先打个素数表来加快求质因数的数量,然后感觉数据太弱了,而且是一组一个测试,感觉打素数表的代价略大,因此没有实现。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    
    using namespace std;
    
    const int max_n = 1000000;
    
    int arr[max_n + 2];
    
    int main()
    {
        //freopen("input.txt", "r", stdin);
        
        int i, j;
        
    //  memset(arr, 0, sizeof(arr));
    //  for(i = 2; i <= sqrt(max_n); ++i)
    //  {
    //      if(!arr[i])
    //      {
    //          j = i + i;
    //          while(j <= max_n)
    //          {
    //              arr[j] = 1;
    //              j += i;
    //          }
    //      }
    //  }
        
    //  for(i = 2; i <= max_n; ++i)
    //  {
    //      if(!arr[i]) printf("%d ", i);
    //  }
        
        int x0, y0;
        scanf("%d%d", &x0, &y0);
        if(y0 % x0 != 0)
        {
            printf("0\n");
        }
        else
        {
            y0 /= x0;
            
            //求质因子
            int count = 0;
            while(y0 != 1)
            {
                for(i = 2; i <= y0; ++i)
                {
                    if(y0 % i == 0) break;
                }
                if(arr[count - 1] != i) arr[count++] = i;
                y0 = y0 / i;
            }
            
            //for(i = 0; i < count; ++i) printf("%d ", arr[i]);
            printf("%.0lf\n", pow(2, count));
        }
        
        //fclose(stdin);
        
        return 0;
    }
    
  • 1
    @ 2018-02-11 18:23:09

    #include<bits/stdc++.h>

    using namespace std;

    int gcd(int x,int y){

    if(y==0)return x;

    return gcd(y,x%y);

    }

    int main(){

    int a,b,ans=0;

    cin>>a>>b;

    for(int i=a;i<=b;i+=a){

    for(int j=a;j<=b;j+=a)

    if(gcd(i,j)==a&&(i/a)*(j/a)*a==b)ans++;

    }

    cout<<ans;

    return 0;

    }

  • 1
    @ 2017-10-21 20:31:57

    #include<bits/stdc++.h>
    using namespace std;
    int a,b,ans;
    int gcd(int aa,int bb)
    {
    return bb==0?aa:gcd(bb,aa%bb);
    }
    int main()
    {
    cin>>a>>b;
    int t=a*b;
    for(int i=2;i<=sqrt(t);i++)
    if(t%i==0&&gcd(t/i,i)==a) ans++;
    cout<<ans*2<<endl;
    return 0;
    }

  • 1
    @ 2017-04-19 13:16:23

    还是比较简单的。

    思路:枚举两个数,当然从 x 开始。

    #include <iostream>
    using namespace std;
    
    int gcd(int m, int n) {
        return n == 0 ? m : gcd(n, m % n);
    }
    
    int lcm(int m, int n) {
        return m * n / gcd(m, n);
    }
    
    int main() {
        int x, y;
        cin >> x >> y;
        int _count = 0;
        for (int i = x; i <= y; i += x)
            for (int j = x; j <= y; j += x)
                if (gcd(i, j) == x && lcm(i, j) == y)
                    _count++;
        cout << _count << endl;
        return 0;
    }
    
    • @ 2017-07-28 11:38:16

      Hack:

      2 1000000
      
  • 0
    @ 2023-05-14 21:15:06

    #include<iostream>
    #include<cmath>
    using namespace std;
    int show(int x0,int y0)
    {
    return x0%y0==0?y0:show(y0,x0%y0);
    }
    int main()
    {
    int x0,y0,P,Q,n,count=0;
    cin>>x0>>y0;
    if(y0%x0!=0)
    {
    cout<<0<<endl;
    return 0;
    }
    else
    {
    n=y0/x0;
    for(P=1;P<=floor(sqrt(n));P++)
    {
    if(n%P==0)
    {
    Q=n/P;
    if(show(Q,P)==1)
    {
    count+=2;
    }
    }
    }
    }

    cout<<count<<endl;
    return 0;
    }

  • 0
    @ 2022-08-16 10:42:20

    两个数的最大公因数和最小公倍数的乘积等于这两个数的乘积

    
    #include<bits/stdc++.h>
    using namespace std;
    int main() {
        int x,y;
        scanf("%d %d",&x,&y);
        int sum=x*y;
        int ans=0;
        for(int i=1;i<=sum;i++) {
            if(sum%i!=0) continue;
            int j=sum/i;
            if(__gcd(i,j)==x) {
                ans++;
            }
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2021-10-08 13:04:33

    #include<iostream>
    using namespace std;
    int x,y;
    int sum;
    int a;
    int ans;
    int gcd(int a,int b)
    {
    return a%b==0?b:gcd(b,a%b);
    }
    int main()
    {
    cin>>x>>y;
    sum=y*x;
    for(int i=1;i<=y/x;++i)
    {
    a=i*x;
    if(sum%a==0&&gcd(a,sum/a)==x) ++ans;
    }
    cout<<ans;
    }

  • 0
    @ 2020-04-08 18:03:00
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    int GetN(int a, int b)
    {
        int t;
        while (b)
        {
            t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
    
    int main()
    {
        int x, y, ans = 0;
        cin >> x >> y;
        int s = x * y;
        for (int i = x; i <= y; i += x)
            for (int j = i; j <= y; j += x)
                if(i * j == s && GetN(i, j) == x)
                {
                    ans++;
                    if(i != j)
                        ans++;
                }
        cout << ans << endl;
    
        return 0;
    }
    
    
  • 0
    @ 2019-07-30 15:52:11

    #include<iostream>
    #include<algorithm>
    using namespace std;

    int gcf(int a,int b){
    return a*b/__gcd(a,b);
    }

    int main(){
    int x,y;
    cin>>x>>y;

    int num=0;
    for(int j=x;j<=y;j+=x){
    for(int i=x;i<=y;i+=x)
    if(__gcd(i,j)==x && gcf(i,j)==y)
    num++;
    }
    cout<<num<<endl;
    return 0;
    }

  • 0
    @ 2018-08-27 21:46:14

    #include<cstdio>
    using namespace std;
    int gys(int a,int b){
    int m;
    do{
    m=a%b;
    a=b;
    b=m;
    }while(m!=0);
    return a;
    }
    int gbs(int c,int d){
    int w=gys(c,d);
    return c*d/w;
    }
    int main(){
    int x,y,count=0;
    scanf("%d %d",&x,&y);
    for(int i=x;i<=y;i++){
    for(int j=i;j<=y;j++){
    if(gys(i,j)==x&&gbs(i,j)==y)
    count++;
    }
    }
    printf("%d",count*2);
    return 0;
    }

  • 0
    @ 2018-08-08 15:36:24

    兄弟们,我回来了,刚刚拿了把三杀!
    var i,j,k,gcd,gbs,t,tot,zs:longint;
    begin
    readln(gcd,gbs);
    if gbs mod gcd<>0 then
    begin
    writeln('0');halt
    end;
    t:=gbs div gcd;
    i:=1;
    while t>1 do
    begin
    inc(i);
    if t mod i=0 then
    begin
    inc(tot);
    while t mod i=0 do t:=t div i;
    end;
    end;
    zs:=trunc(exp(ln(2)*tot));
    writeln(zs);
    end.
    本来有一个超时后来改了一下,这是修改版

  • 0
    @ 2018-04-26 15:07:05

    看到你们的题解千篇一律,代码基本一样,我就笑笑。

    其实这是一个数学题目,枚举什么的不是因为数据量小,否则要呵呵。
    如果最大公约数是a,最小公倍数是b,如果b不能被a整除,那说明不可能有存在答案,所以结果是0。
    否则设C = B/A,将C质因数分解,得到的不同质数的个数D,例如C=12,那D=2(2个2,1个3),那D个质数将要么给a,要么给b,因此结果就是2^D,ps:同一个质数不能各分一边,否则最大公约数将不再是b。

  • 0
    @ 2018-01-27 14:53:44
    #include <cstdio>
    using namespace std;
    int x, y, cnt;
    
    int gcd(int m, int n){return n == 0 ? m : gcd(n, m % n);}
    inline int lcm(int m, int n){return m * n / gcd(m, n);}
    int main(){
        scanf("%d %d", &x, &y);
        for (int i = x; i <= y; i += x){
            for (int j = x; j <= y; j += x){
                if (gcd(i, j) == x && lcm(i, j) == y) cnt++;
            }
        }
        printf("%d\n", cnt);
        return 0;
    }
    
    
  • 0
    @ 2017-12-13 14:12:01

    #include<iostream>
    #include<cmath>
    using namespace std;
    int m,n,ans;
    int gcd(int x,int y)
    {
    if(y==0) {return x;}
    return gcd(y,x%y);
    }
    int main()
    {
    cin>>n>>m;
    for(int i=1;i<=sqrt(m*n);i++)
    {
    if((n*m)%i==0&&gcd(i,(n*m)/i)==n) ans++;
    }
    cout<<ans*2;
    return 0;
    }

  • 0
    @ 2017-11-01 16:36:45

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a(int m,int n){//最大公约数
    if(m<n) swap(m,n);
    for(int i=n;i>=1;i--){
    if(m%i==0 && n%i==0) {
    return i;
    }
    }
    }
    int b(int m,int n){//最小公倍数
    return m*n/a(m,n);
    }
    int main() {
    int x,y;
    cin>>x>>y;
    int count=0;
    for(int i=x;i<=y;i+=x)
    for(int j=x;j<=y;j+=x)
    if(a(i,j)==x && b(i,j)==y)
    count++;
    cout<<count;
    return 0;
    }

  • 0
    @ 2017-11-01 16:36:09

    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a(int m,int n){
    if(m<n) swap(m,n);
    for(int i=n;i>=1;i--){
    if(m%i==0 && n%i==0) {
    return i;
    }
    }
    }
    int b(int m,int n){
    return m*n/a(m,n);
    }
    int main() {
    int x,y;
    cin>>x>>y;
    int count=0;
    for(int i=x;i<=y;i+=x)
    for(int j=x;j<=y;j+=x)
    if(a(i,j)==x && b(i,j)==y)
    count++;
    cout<<count;
    return 0;
    }

  • 0
    @ 2015-02-02 19:07:55

    #include <iostream>
    using namespace std;
    int yue[10001];
    int gcd(int m, int n);
    int lcm(int m, int n);
    int main()
    {
    int x, y, cnt = 0, dex = 0;
    cin >> x >> y;
    for (int i = 2; i <= y; i++)
    {
    if (y % i == 0)
    {
    yue[dex++] = i;
    }
    }
    for (int i = 0; i < dex; i++)
    for (int j = 0; j < dex; j++)
    if (gcd(yue[i], yue[j]) == x && lcm(yue[i], yue[j]) == y)
    cnt++;
    cout << cnt << endl;
    }

    int gcd(int m, int n)//最大公约数,更相减损法

    {

    while (m != n)

    {

    if (m>n) m -= n;

    else n -= m;

    }

    return m;

    }

    int lcm(int m, int n)//最小公倍数

    {

    int i;

    for (i = (m>n ? m : n);; i++)

    if (i%m == 0 && i%n == 0)

    return i;

    }

    简单的搜索,但是不能直接在范围内搜索,那样太费事,这里用点数学方法选出一些数。
    如果两个数的最小公倍数是y,那么这两个数是y的约数。
    将y的约数筛选出来,再搜索即可

最小公倍数和最大公约数问题

信息

ID
1131
难度
4
分类
其他 | 数学搜索 | 枚举 点击显示
标签
递交数
7315
已通过
2972
通过率
41%
被复制
25
上传者