Building a gear train

from math import gcd  r_in, r_out = map(int, input().split())m = int(input())teeth = list(map(int, input().split()))stages = [(a, b) for a in teeth for b in teeth if a != b]  # (구동 기어, 따라 도는 기어) g = gcd(r_out, r_in)want = (r_out // g, r_in // g)  # 바라는 비 = 출력 / 입력, 기약분수로  def count_trains(start, left, num, den):    """stages[start:]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 want가 되는 열차 수.    고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다."""    if left == 0:        return 1 if (num, den) == want else 0    total = 0    for i in range(start, len(stages)):        a, b = stages[i]        n2, d2 = num * a, den * b        c = gcd(n2, d2)        total += count_trains(i, left - 1, n2 // c, d2 // c)  # 늘 기약분수로 줄여 둔다    return total  answer = "-1"for k in range(4):    c = count_trains(0, k, 1, 1)    if c > 0:        answer = f"{k} {c}"        breakprint(answer)

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [rIn, rOut, m] = data;const teeth = data.slice(3, 3 + m); function gcd(a, b) {  while (b !== 0) [a, b] = [b, a % b];  return a;} const stages = []; // [구동 기어, 따라 도는 기어]for (const a of teeth) for (const b of teeth) if (a !== b) stages.push([a, b]); const g = gcd(rOut, rIn);const wantNum = rOut / g; // 바라는 비 = 출력 / 입력, 기약분수로const wantDen = rIn / g; // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.// 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다function countTrains(start, left, num, den) {  if (left === 0) return num === wantNum && den === wantDen ? 1 : 0;  let total = 0;  for (let i = start; i < stages.length; i++) {    const [a, b] = stages[i];    const c = gcd(num * a, den * b);    total += countTrains(i, left - 1, (num * a) / c, (den * b) / c); // 늘 기약분수로 줄여 둔다  }  return total;} let answer = "-1";for (let k = 0; k <= 3; k++) {  const c = countTrains(0, k, 1, 1);  if (c > 0) {    answer = `${k} ${c}`;    break;  }}console.log(answer);

import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [rIn, rOut, m] = data;const teeth: number[] = data.slice(3, 3 + m); function gcd(a: number, b: number): number {  while (b !== 0) [a, b] = [b, a % b];  return a;} const stages: [number, number][] = []; // [구동 기어, 따라 도는 기어]for (const a of teeth) for (const b of teeth) if (a !== b) stages.push([a, b]); const g = gcd(rOut, rIn);const wantNum = rOut / g; // 바라는 비 = 출력 / 입력, 기약분수로const wantDen = rIn / g; // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.// 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다function countTrains(start: number, left: number, num: number, den: number): number {  if (left === 0) return num === wantNum && den === wantDen ? 1 : 0;  let total = 0;  for (let i = start; i < stages.length; i++) {    const [a, b] = stages[i];    const c = gcd(num * a, den * b);    total += countTrains(i, left - 1, (num * a) / c, (den * b) / c); // 늘 기약분수로 줄여 둔다  }  return total;} let answer = "-1";for (let k = 0; k <= 3; k++) {  const c = countTrains(0, k, 1, 1);  if (c > 0) {    answer = `${k} ${c}`;    break;  }}console.log(answer);

import java.util.*; public class Main {    static List<int[]> stages = new ArrayList<>(); // {구동 기어, 따라 도는 기어}    static long wantNum, wantDen;     static long gcd(long a, long b) {        while (b != 0) {            long t = a % b;            a = b;            b = t;        }        return a;    }     // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.    // 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다    static long countTrains(int start, int left, long num, long den) {        if (left == 0) return num == wantNum && den == wantDen ? 1 : 0;        long total = 0;        for (int i = start; i < stages.size(); i++) {            long n2 = num * stages.get(i)[0], d2 = den * stages.get(i)[1];            long c = gcd(n2, d2);            total += countTrains(i, left - 1, n2 / c, d2 / c); // 늘 기약분수로 줄여 둔다        }        return total;    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long rIn = sc.nextLong(), rOut = sc.nextLong();        int m = sc.nextInt();        int[] teeth = new int[m];        for (int i = 0; i < m; i++) teeth[i] = sc.nextInt();        for (int a : teeth)            for (int b : teeth)                if (a != b) stages.add(new int[] {a, b});        long g = gcd(rOut, rIn);        wantNum = rOut / g; // 바라는 비 = 출력 / 입력, 기약분수로        wantDen = rIn / g;        String answer = "-1";        for (int k = 0; k <= 3; k++) {            long c = countTrains(0, k, 1, 1);            if (c > 0) {                answer = k + " " + c;                break;            }        }        System.out.println(answer);    }}

using System;using System.Collections.Generic;using System.Linq; class Program{    static readonly List<(long a, long b)> stages = new List<(long a, long b)>(); // (구동 기어, 따라 도는 기어)    static long wantNum, wantDen;     static long Gcd(long a, long b)    {        while (b != 0) (a, b) = (b, a % b);        return a;    }     // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.    // 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다    static long CountTrains(int start, int left, long num, long den)    {        if (left == 0) return num == wantNum && den == wantDen ? 1 : 0;        long total = 0;        for (int i = start; i < stages.Count; i++)        {            long n2 = num * stages[i].a, d2 = den * stages[i].b;            long c = Gcd(n2, d2);            total += CountTrains(i, left - 1, n2 / c, d2 / c); // 늘 기약분수로 줄여 둔다        }        return total;    }     static void Main()    {        long[] r = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(long.Parse).ToArray();        Console.ReadLine();        int[] teeth = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray();        foreach (int a in teeth)            foreach (int b in teeth)                if (a != b) stages.Add((a, b));        long g = Gcd(r[1], r[0]);        wantNum = r[1] / g; // 바라는 비 = 출력 / 입력, 기약분수로        wantDen = r[0] / g;        string answer = "-1";        for (int k = 0; k <= 3; k++)        {            long c = CountTrains(0, k, 1, 1);            if (c > 0)            {                answer = k + " " + c;                break;            }        }        Console.WriteLine(answer);    }}

#include <iostream>#include <numeric>#include <utility>#include <vector> std::vector<std::pair<long long, long long>> stages;  // (구동 기어, 따라 도는 기어)long long wantNum, wantDen; // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.// 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다long long countTrains(size_t start, int left, long long num, long long den) {    if (left == 0) return num == wantNum && den == wantDen ? 1 : 0;    long long total = 0;    for (size_t i = start; i < stages.size(); i++) {        long long n2 = num * stages[i].first, d2 = den * stages[i].second;        long long c = std::gcd(n2, d2);        total += countTrains(i, left - 1, n2 / c, d2 / c);  // 늘 기약분수로 줄여 둔다    }    return total;} int main() {    long long rIn, rOut;    int m;    std::cin >> rIn >> rOut >> m;    std::vector<long long> teeth(m);    for (auto& t : teeth) std::cin >> t;    for (long long a : teeth)        for (long long b : teeth)            if (a != b) stages.push_back({a, b});    long long g = std::gcd(rOut, rIn);    wantNum = rOut / g;  // 바라는 비 = 출력 / 입력, 기약분수로    wantDen = rIn / g;    for (int k = 0; k <= 3; k++) {        long long c = countTrains(0, k, 1, 1);        if (c > 0) {            std::cout << k << ' ' << c << '\n';            return 0;        }    }    std::cout << "-1\n";}

#include <stdio.h> static int sa[56], sb[56], nstages = 0; /* 단: 구동 기어 sa, 따라 도는 기어 sb */static long long want_num, want_den; long long gcd(long long a, long long b) {    while (b != 0) {        long long t = a % b;        a = b;        b = t;    }    return a;} /* 단 start번부터 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.   고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다 */long long count_trains(int start, int left, long long num, long long den) {    if (left == 0) return num == want_num && den == want_den;    long long total = 0;    for (int i = start; i < nstages; i++) {        long long n2 = num * sa[i], d2 = den * sb[i];        long long c = gcd(n2, d2);        total += count_trains(i, left - 1, n2 / c, d2 / c); /* 늘 기약분수로 줄여 둔다 */    }    return total;} int main(void) {    long long r_in, r_out;    int m, teeth[8];    scanf("%lld %lld %d", &r_in, &r_out, &m);    for (int i = 0; i < m; i++) scanf("%d", &teeth[i]);    for (int i = 0; i < m; i++)        for (int j = 0; j < m; j++)            if (i != j) {                sa[nstages] = teeth[i];                sb[nstages++] = teeth[j];            }    long long g = gcd(r_out, r_in);    want_num = r_out / g; /* 바라는 비 = 출력 / 입력, 기약분수로 */    want_den = r_in / g;    for (int k = 0; k <= 3; k++) {        long long c = count_trains(0, k, 1, 1);        if (c > 0) {            printf("%d %lld\n", k, c);            return 0;        }    }    puts("-1");    return 0;}

최대공약수(a, b){    while (b != 0)    {        t = a % b;        a = b;        b = t;    }    return a;} // stages[start..]에서 left개를 더 골라(같은 단 여러 번 가능) 비가 바라는 비가 되는 열차 수.// 고른 단의 번호가 줄지 않게 해서, 순서만 바뀐 열차를 두 번 세지 않는다열차세기(start, left, num, den){    if (left == 0)    {        if (num == wantNum && den == wantDen)        {            return 1;        }        return 0;    }    total = 0;    for (s = start; s < stages.Count; s++)    {        n2 = num * stages[s][0];        d2 = den * stages[s][1];        c = 최대공약수(n2, d2);        total += 열차세기(s, left - 1, n2 / c, d2 / c); // 늘 기약분수로 줄여 둔다(나누어떨어져서 / 로 된다)    }    return total;} r = Console.ReadNumbers();rIn = r[0];rOut = r[1];m = Console.ReadLine().ToNumber();teeth = Console.ReadNumbers();stages = []; // [구동 기어, 따라 도는 기어]foreach (a in teeth){    foreach (b in teeth)    {        if (a != b)        {            stages.Add([a, b]);        }    }}g = 최대공약수(rOut, rIn);wantNum = rOut / g; // 바라는 비 = 출력 / 입력, 기약분수로wantDen = rIn / g;answer = "-1";for (k = 0; k <= 3; k++){    cnt = 열차세기(0, k, 1, 1);    if (cnt > 0)    {        answer = k + " " + cnt;        break;    }}Console.WriteLine(answer);