Клуб по състезателно програмиране
Бургаски Свободен Университет

Problem Statement for FoxAndGCDLCM

На 19.4.2012г. в клуба по състезателно програмиране беше решена една доста интересна задача, условието го има на ТОЗИ адрес. Но сайта изисква регистрация, така ,че съм го сложил отдолу ,а сорса на решението след това. Този път ще бъде качен бонус материал, снимка от трудовия процес върху алгоритъма за задачата. От сега предупреждавам, че е доста абстрактно.

P.S. Задачата я намерихме на сайта на Киров.

Условие:

 Problem Statement for FoxAndGCDLCM

Problem Statement

Fox Jiro and Eel Saburo are good friends. One day Saburo found two interesting positive integers: A and B.

On the next day, Saburo met Jiro and wanted to tell him the two integers. However, he managed to forget their values. All Saburo could remember was their greatest common divisor G and their least common multiple L.

You are given two longs: G and L. Find the original integers A and B, and return the value of A+B. If there are multiple pairs of A and B that correspond to G and L, pick the one that minimizes A+B. If it is impossible to find such A and B (i.e., Saburo made a mistake somewhere), return -1.

Definition

Class: FoxAndGCDLCM
Method: get
Parameters: long, long
Returns: long
Method signature: long get(long G, long L)
(be sure your method is public)

Notes

The greatest common divisor of two integers a and b is the largest positive integer that divides both a and b without any remainder.
The least common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b.

Constraints

G will be between 1 and 1,000,000,000,000 (10^12), inclusive.
L will be between 1 and 1,000,000,000,000 (10^12), inclusive.

 

Сорс:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    unsigned long long NOK,NOD;
    cin>>NOD>>NOK;
    const unsigned long long N=NOK/NOD;
    bool a[N];
    for(int i = 0; i<N; i++) a[i] = 1;
    for(int i=2; i<sqrt(N); i++){
        if(a[i] == 1){
            for(int j=2*i; j<N; j++){
            if(j%i == 0) a[j] = 0;
            }
        }
    }
unsigned long long MIN=999999999;
for(int i=1;i<N/2;i++)
{
      if(a[i] == 1)
      {
        if((NOK/NOD)%i==0){
        if(NOD*i+NOK/i<MIN) { MIN=NOD*i+NOK/i; }}
      }
}
cout<<MIN;
     return 0;
}


Бонус материал :

Клуб по състезателно програмиране 19.4.2012г.

Клуб по състезателно програмиране 19.4.2012г.

 

 

Поздрави, Стоян Узунов.

Comments are closed.