题解 - Vijos

5

3g93zhmq (3g93zhmq) LV 8 @ 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

w568w LV 8 @ 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

猫粮寸断 LV 10 @ 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

mobileliker LV 7 @ 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

SUL LV 4 @ 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

Randle LV 9 @ 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

larryzhong LV 9 @ 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;
}

q234rty @ 2017-07-28 11:38:16
Hack:
```
2 1000000
```

0

J o e (唐子瞳) LV 10 @ 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

Doria LV 8 @ 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

Plex LV 3 @ 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

Jong-oo LV 8 @ 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

dzz751593 LV 7 @ 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

第三个柯菲 LV 5 @ 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

斩魂 LV 7 @ 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

ZeroZerg LV 8 @ 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

JimmyChen LV 8 @ 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

614350023 LV 8 @ 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

18017894 (18017894) LV 8 @ 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

18017894 (18017894) LV 8 @ 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

chuanxin495 LV 7 @ 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的约数筛选出来，再搜索即可

题解

193 条题解

}

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

信息

状态

开发

支持

题解

193 条题解

}

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

信息

状态

开发

支持

还没有账户？

登录