Найти количество пар чисел с заданным НОК

258

20 декабря 2017, 22:27

У меня есть число N - наименьшее общее кратное двух чисел a и b.

Нужно найти сколько пар чисел a и b может быть. Например, если N = 6, то есть 9 комбинаций: (1,6),(2,6),(3,6),(6,3),(6,2),(6,1),(2,3),(3,2),(6,6).

Вот на чем я остановился:

#include <iostream>
using namespace std;
int main() {
int X,count = 0;
cin >> X;
int i = 1;
while (true) {
    if (X/i <= 1) {
        break;
    }
    if (X%i == 0) {
        count += 2;
        if (X%(X/i) == 0) {
            count++;
        }
    }       
    i++;
}   
cout << count << endl;  
return 0;
}

Answer 1

sory у меня готовая есть только на Java что странно. С двум`я цифрами как у вас А на С++ первым аргументом вы вводите сколько цифр у вас будет в вашем случаи первый аргумент всегда 2 Мотыжите переделать себе

C++

 #include <math.h>
    #include <string.h>
    #include <iostream.h>
    #include <stdio.h>
    #include <stdlib.h>
    int a[101]={0};
    int b[100001]={0};
    int c[101]={0};
    int main()
    {
    int z,r,m,n,i,j,k,s,y,x;
    cin>>n;
    cin>>x;
    z=0;
    while (x>1)
    {
    for (i=2;i<=x;i++)
    if (x%i==0)
    {
    x/=i;b[z++]=i;break;
    }
    }
    for (m=1;m<n;m++)
    {
    cin>>x;
    r=0;
    while (x>1)
    {
    for (i=2;i<=x;i++)
    if (x%i==0)
    {
    x/=i;c[r++]=i;break;
    }
    }
    for (i=0;i<z;i++)
    for (j=0;j<r;j++)
    if (b[i]==c[j])
    {
    c[j]=0;break;
    }
    for (i=0;i<r;i++)
    if (c[i]!=0) b[z++]=c[i];
    }
    a[0]=1;
    y=0;
    for (k=0;k<z;k++)
    {
    for (i=0;i<=y;i++)
    a[i]*=b[k];
    for (i=0;i<=y;i++)
    if (a[i]>9)
    {
    if (i==y)y++; a[i+1]+=a[i]/10;a[i]=a[i]%10;
    }
    }
    for (i=y;i>=0;i--)
    {
    cout<<a[i];
    }
    cout<<endl;
    getchar(); getchar();
    return 0;
    }

java

import java.util.Scanner;
public class Main {
    public static void main(String[] args) 
    {
        //int x1,y1,x2,y2,x3,y3,x4,y4;
        Scanner in = new Scanner(System.in);
        /*x4 = in.nextInt();
        y4 = in.nextInt();
        x1 = in.nextInt();
        y1 = in.nextInt();
        x2 = in.nextInt();
        y2 = in.nextInt();
        x3 = in.nextInt();
        y3 = in.nextInt();*/

 int a[] = new int[12];     
 int b[] = new int [100001];
 int c[] = new int [101];
 int z,r,m,n,i,j,k,s,y,x;
 n = 2;
 x = in.nextInt();
 z=0;

while (x>1)
{
for (i=2;i<=x;i++)
if (x%i==0)
{
x/=i;b[z++]=i;break;
}
}

for (m=1;m<n;m++)
{
 x = in.nextInt();
r=0;
while (x>1)
{
for (i=2;i<=x;i++)
if (x%i==0)
{
x/=i;c[r++]=i;break;
}
}
for (i=0;i<z;i++)
for (j=0;j<r;j++)
if (b[i]==c[j])
{
c[j]=0;break;
}
for (i=0;i<r;i++)
if (c[i]!=0) b[z++]=c[i];
}
a[0]=1;
y=0;
for (k=0;k<z;k++)
{
for (i=0;i<=y;i++)
a[i]*=b[k];
for (i=0;i<=y;i++)
if (a[i]>9)
{
if (i==y)y++; a[i+1]+=a[i]/10;a[i]=a[i]%10;
}
}
for (i=y;i>=0;i--)
{
System.out.printf("" + a[i]);
}
System.out.printf("\n" );

    }
}