Diberikan dua bilangan bulat positif adan b, menghasilkan dua bilangan bulat positif cdan dsedemikian rupa sehingga:

• c membagi a
• d membagi b
• c dan d co-prime
• yang paling umum beberapa dari cdan dsama dengan beberapa paling umum dari adan b.

Jika ada lebih dari satu jawaban yang mungkin, Anda hanya dapat menampilkan satu atau semua jawaban.

Kasus uji:

 a  b  c  d
12 18  4  9
18 12  9  4
 5  7  5  7
 3  6  1  6 or 3 2
 9  9  9  1 or 1 9
 6 15  2 15 or 6 5
 1  1  1  1

Ini adalah kode-golf . Jawaban terpendek dalam byte menang.

Jelly , 21 13 byte

ÆEz®0iṂ$¦€ZÆẸ

Cobalah online!

Jika a = 2 ^A · 3 ^B · 5 ^C ·… dan b = 2 ^α · 3 ^β · 5 ^γ ·… , maka kami menghitung

• c = 2 ^{A> α? A: 0} · 3 ^{B> β? B: 0} · 5 ^{C> γ? C: 0} ·…

• d = 2 ^{A> α? 0: α} · 3 ^{B> β? 0: β} · 5 ^{C> γ? 0: γ} ·…

Sekarang lcm (c, d) = 2 ^{maks (A> α? A: 0, A> α? 0: α)} ·… = 2 ^{maks (A, α)} · 3 ^{maks (B, β)} ·… = lcm ( a, b)

dan gcd (c, d) = 2 ^{mnt (A> α? A: 0, A> α? 0: α)} ·… = 2 ⁰ · 3 ⁰ · 5 ⁰ ·… = 1 .

Dengan kata lain: mulai dari (c, d) = (a, b) . Kemudian, untuk masing-masing prime, bagi prime itu semua jalan keluar dari faktorisasi c atau d : mana yang memiliki eksponen terkecil untuk prime itu. (Dalam implementasi ini, dalam kasus seri, c kehilangan eksponennya.)

Jadi jika a = 2250 = 2 ¹ · 3 ² · 5 ³ dan b = 360 = 2 ³ · 3 ² · 5 ¹ ,

maka c = 2 ⁰ · 3 ⁰ · 5 ³ = 125 dan d = 2 ³ · 3 ² · 5 ⁰ = 72 .

Jonathan Allan bermain golf sebanyak 8 byte! Terima kasih ~

R, 143 139 123 byte

f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")

(Terima kasih kepada @Giuseppe untuk off 19 byte itu!)

Dengan lekukan, baris baru, dan beberapa penjelasan:

f=function(a,b,
           q=1:(a*b)) #Defined as function arguments defaults to avoid having to use curly brackets
    for(i in 1:a)
        for(j in 1:b)
            if(!a%%i + b%%j & #Is a divided by c and b divided by d
               max(q[!i%%q+j%%q])<2 & #Are c and d coprimes
               i*j==min(q[!q%%a+q%%b])) #Is this the same lcm
                   cat(i,j,"\n") #Then print

Kasus uji:

> f=function(a,b,q=1:(a*b))for(i in 1:a)for(j in 1:b)if(!a%%i+b%%j&max(q[!i%%q+j%%q])<2&i*j==min(q[!q%%a+q%%b]))cat(i,j,"\n")
> f(5,7)
5 7 
> f(12,18)
4 9 
> f(6,15)
2 15 
6 5 
> f(1,1)
1 1 

Sekam , 10 byte

→ÖF§-⌋⌉ΠmḊ

Paksaan. Mengambil dan mengembalikan daftar, dan bekerja untuk lebih dari dua angka juga. Cobalah online!

Penjelasan

→ÖF§-⌋⌉ΠmḊ  Implicit input, say [6,15]
        mḊ  Map divisors: [[1,2,3,6],[1,3,5,15]]
       Π    Cartesian product:[[1,1],[2,1],[1,3],[2,3],[3,1],[1,5],[3,3],[6,1],[1,15],[2,5],[3,5],[6,3],[2,15],[6,5],[3,15],[6,15]]
 Ö          Sort by
  F         reduce by
     ⌉      lcm
   -⌋       minus gcd: [[1,1],[3,3],[2,1],[1,3],[3,1],[6,3],[1,5],[2,3],[6,1],[2,5],[3,15],[1,15],[3,5],[6,15],[2,15],[6,5]]
→           Get last element: [6,5]

Mathematica, 82 byte

#&@@Select[Subsets[Flatten@Divisors[{t=#,r=#2}],{2}],GCD@@#==1&&LCM@@#==t~LCM~r&]&

JavaScript (ES6), 90 84 80 byte

Mengambil input dalam sintaks currying (a)(b) dan mengembalikan array 2 integer.

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

Uji kasus

let f =

a=>g=(b,c=1)=>(G=(a,b)=>b?G(b,a%b):a)(c,d=a*b/G(a,b)/c)-1|a%c|b%d?g(b,c+1):[c,d]

console.log(JSON.stringify(f(12)(18))) // [ 4,  9 ]
console.log(JSON.stringify(f(18)(12))) // [ 9,  4 ]
console.log(JSON.stringify(f( 5)( 7))) // [ 5,  7 ]
console.log(JSON.stringify(f( 3)( 6))) // [ 1,  6 ] or [ 3, 2 ]
console.log(JSON.stringify(f( 9)( 9))) // [ 9,  1 ] or [ 1, 9 ]
console.log(JSON.stringify(f( 6)(15))) // [ 2, 15 ] or [ 6, 5 ]
console.log(JSON.stringify(f( 1)( 1))) // [ 1,  1 ]

Bagaimana?

a =>                            // a = first input
  g = (                         // g = recursive function that takes:
    b,                          //   b = second input
    c = 1                       //   c = first output divisor, initially set to 1
  ) =>                          //
    (G = (a, b) =>              // G = function that takes a and b
      b ? G(b, a % b) : a       //     and returns the greatest common divisor
    )(                          // we call it with:
      c,                        //   - c
      d = a * b / G(a, b) / c   //   - d = LCM(a, b) / c = a * b / GCD(a, b) / c
    ) - 1 |                     // if the result is not 1 (i.e. c and d are not coprime)
    a % c |                     // or c does not divide a
    b % d ?                     // or d does not divide b:
      g(b, c + 1)               //   do a recursive call with c + 1
    :                           // else:
      [c, d]                    //   return [c, d], a valid factorization of the LCM

MATL , 17 16 byte

&YFt&X>2:!=*^!Xp

Cobalah online!

Metode yang sama dengan solusi Lynn's Jelly

Sudah lama sejak saya menggunakan MATL (atau matlab dalam hal ini) begitu banyak perbaikan yang mungkin dilakukan.

Haskell ,50 48 47 45 42 byte

(?)=gcd;a!b|c<-div a$a?b=(c*c?b,div b$c?b)

Ide: Saya perhatikan itu c*d = a*b/gcd(a,b). Jadi algoritma melakukan dua langkah:

1. Mulai dengan c' = a/gcd(a,b)dan d' = b. Ini memenuhi semua persyaratan kecuali itu c'dan d'harus co-prime.
2. Untuk membuatnya co-prime, saya menghitung e = gcd(c',d')lalu mengatur c = c'*edan d = d'/e. Ini membuat semua properti (karena faktor gabungan tetap sama), tetapi karena saya menghapus semua faktor yang dibagikan d, saya membuat cdan dcoprime.

Dalam implementasi saya, c'baru saja dipanggil c.

Cobalah online!

-3 byte terima kasih kepada Laikoni

05AB1E , 12 byte

Ñ`âʒ.¿I.¿Q}н

Cobalah online! atau sebagai Test suite

R , 126 byte

function(a,b,g=function(x,y)ifelse(o<-x%%y,g(y,o),y),l=a*b/g(a,b))matrix(c(C<-(1:l)[!l%%1:l],D<-l/C),,2)[g(C,D)<2&!a%%C+b%%D,]

Cobalah online!

Ini mengambil pendekatan yang berbeda (dan tampaknya kurang golf) untuk menemukan nilai daripada jawaban R lainnya .

Penjelasan:

function(a,b){
 G <- function(x,y)ifelse(o<-x%%y,G(y,o),y) #gcd function, vectorized for x,y
 l <- a*b/g(a,b)                            #lcm of a,b
 C <- (1:l)[!l%%1:l]                        #divisors of l
 D <- l/C                                   #l/C is the other half of the pair
 rel_prime <- G(C, D) < 2                   #pairs where C,D are relatively prime, lol, GCD
 a_div <- !a%%C                             #divisors of a
 b_div <- !b%%D                             #divisors of b
 C <- C[rel_prime & a_div & b_div]
 D <- D[rel_prime & a_div & b_div]          #filter out the bad pairs
 matrix(c(C,D),,ncol = 2)                   #matrix of pairs, returned
}

kecuali saya shoehorn semua definisi sebagai argumen default dan melakukan semua perhitungan pada satu baris untuk golfiness.

J , 19 byte

(*/:"1)&.|:&.(_&q:)

Cobalah online!

Berdasarkan solusi @ Lynn .

Penjelasan

(*/:"1)&.|:&.(_&q:)  Input: [a, b]
              _&q:   Get exponenets of each prime
         |:&         Transpose
  /:"1 &             Grade each row
 *                   Multiply elementwise
       &.|:          Transpose
           &. _&q:   Convert exponents back to numbers

Haskell , 91 74 byte

a!b=[(x,y)|x<-[1..a],y<-[1..b],rem a x+rem b y+gcd x y<2,lcm a b==lcm x y]

Cobalah online!

Disimpan 17 byte berkat Laikoni

Python 2 , 75 byte

def f(x):n=1;exec'n+=1;j=k=1\nwhile x[j]%k<1:k*=n**j;j^=1\nx[j]/=k/n;'*x[0]

Input diambil sebagai daftar, yang diubah fungsi pada tempatnya.

Cobalah online!

Python 3 , 129 byte

lambda a,b:[[c,d]for c in range(1,-~a)for d in range(1,-~b)if((gcd(c,d)<2)*a*b/gcd(a,b)==c*d/gcd(c,d))>a%c+b%d]
from math import*

Cobalah online! atau Coba test suite.

Keluarkan semua kombinasi yang mungkin dalam bentuk daftar bersarang.

Jelly ,  19 15  14 byte

-4 dengan pointer dari Leaky Nun (gunakan pembagi bawaan)

^{Saya hampir 100% yakin ini bukan cara untuk benar-benar melakukan ini, tetapi di sini adalah upaya pertama.
Mari kita lihat siapa yang mengalahkannya dengan tujuh atau delapan byter!
Yap ... lihat jawaban Lynn dengan penjelasan!}

g/־l/
ÆDp/ÇÐṂ

Tautan monadik mengambil daftar dari dua angka dan mengembalikan daftar daftar kemungkinan.

Cobalah online!

Bagaimana?

g/־l/  - Link: gcd divided by lcm: list [x, y]
g/      - reduce by gcd = gcd(x, y)
   æl/  - reduce by lcm = lcm(x,y)
  ÷     - divide

ÆDp/ÇÐṂ - Main link: list [a, b]    e.g. [160, 90]
ÆD      - divisors (vectorises)          [[1,2,4,5,8,10,16,20,32,40,80,160],[1,2,3,5,6,9,10,15,18,30,45,90]]
  p/    - reduce by Cartesian product    [[1,1],[1,2],...,[1,90],[2,1],[2,2],...,[2,90],....,[160,90]]
     ÐṂ - entries for which this is minimal:
    Ç   -   call the last link (1) as a monad

Perl 6 , 72 byte

{([X] map {grep $_%%*,1..$_},@^a).grep:{([lcm] @a)==([lcm] $_)==[*] $_}}

Cobalah online!

Mengambil daftar (a, b). Mengembalikan daftar semua daftar yang mungkin (c, d).

Penjelasan:

-> @ab {
    # Generate all pairs (c, d)
    ([X]
         # where c divides a and d divides b.
         map { grep $_%%*, 1..$_ }, @ab)
    # Only keep pairs with lcm(a, b) = lcm(c, d) and lcm(c, d) = c * d.
    # The latter implies gcd(c, d) = 1.
    .grep: { ([lcm] @ab) == ([lcm] $_) == [*] $_ }
}

Python 2 , 126 121 byte

def f(a,b):
 c=[1,1];p=2
 while p<=a*b:
	t=m=1
	while(a*b)%p<1:m*=p;t=b%p<1;a/=p**(a%p<1);b/=p**t
	p+=1;c[t]*=m
 return c

Cobalah online!

Python 2 + sympy , 148 byte

from sympy import*
a,b=input()
c=d=z=1
while(a/c*c+b/d*d<a+b)+gcd(c,d)-1+(lcm(c,d)!=lcm(a,b)):E=c==d==z;Q=c==z;d=+E or Q+d;c=+Q or-~c;z+=E
print c,d

Cobalah online!

-1 terima kasih kepada Jonathan Frech .

Jawaban ini bekerja di Python 2 (bukan Python 3), menggunakan sympy.gcddan sympy.lcmbukannya math.gcddan math.lcmyang hanya tersedia di Python 3. Dan ya, ini adalah kekuatan brutal :)

Jelly, 13 bytes

Ụ€’×
ÆEz0ÇZÆẸ

Try it online! My first Jelly answer! Edit: ÆEz0µỤ€’×µZÆẸ also works for 13 bytes. Explanation:

ÆE              Get prime factor exponents of both values (vectorises)
  z0            Zip but fill the shorter array with 0
    µ           New monadic link
     Ụ€         Grade up each pair (1-indexed)
       ’        Convert to 0-indexing (vectorises)
        ×       Multiply each pair by its grade (vectorises)
         µ      New monadic link
          Z     Zip back into separate lists of prime factor exponents
           ÆẸ   Turn prime exponent lists back into values (vectorises)

PARI/GP, 86 bytes

This just does what Lynn says in her answer:

f(a,b)=forprime(p=2,a*b,v=valuation(a,p);w=valuation(b,p);if(w<v,b/=p^w,a/=p^v));[a,b]

If I do not count the f(a,b)= part, it is 79 bytes.

05AB1E, 32 26 24 22 20 19 bytes

Ó0ζεD`›0sǝ}øεā<ØsmP

Try it online! I still have no idea how to write in this language, but at least it's not a brute-force algorithm. Explanation:

Ó                       Get exponents of prime factors (vectorised)
 0ζ                     Zip, filling with 0
   ε      }             For each prime
    D`                  Extract the pair of exponents
      ›0sǝ              Overwrite the smaller with 0
           ø            Zip back into two lists of prime exponents
            ε           For each list (} implied)
             ā<Ø        Get a list of primes
                sm      Raise each prime to the exponent
                  P     Take the product