Small Operations node.js

gistfile1.txt

const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
const lines = []
rl.on('line', (input) => {
    lines.push(input);
})
rl.on('close', () => {
// (function() {
    // const lines = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')
    let l = 0;
    let t = 1
    t = +lines[l++]
    const output = []
    for (let i = 0; i < t; i++) {
        const [x, y, k] = lines[l++].trim().split(' ').map(Number)
        output[i] = solve(x, y, k)
    }
    console.log(output.join('\n'))
// })()
})

// let ds
// pre(1e6)
// function pre(n) {
//     ds = Array(n + 1)
//         .fill(0)
//         .map(() => [])
//     for (let i = 1; i <= n; i++) {
//         for (let j = i; j <= n; j += i) {
//             ds[j].push(i)
//         }
//     }
// }

function solve(x, y, k) {
    const g = gcd(x, y)
    const a = cal(x / g)
    const b = cal(y / g)
    const ans = a + b
    return ans === Infinity ? -1 : ans

    function cal(n) {
        const o = []
        for (let i = 1; i * i <= n; i++) {
            if (n % i) continue
            o.push(i)
            o.push(n / i)
        }
        o.sort((a, b) => a - b)
        // console.log(o)
        //
        const dp = Array(o.length)
        for (let i = 0; i < o.length; i++) {
            let temp = Infinity
            for (let j = 0; j < i; j++) {
                if (!(o[i] % o[j]) && o[i] / o[j] <= k) {
                    temp = Math.min(temp, dp[j])
                }
            }
            dp[i] = Math.min(o[i] <= k ? (o[i] === 1 ? 0 : 1) : Infinity, temp + 1)
        }
        // console.log(o, dp)
        return dp[o.length - 1]
    }
}
function gcd(a, b) {
    if (a === 0) return b
    if (b === 0) return a

    while (a) {
        const r = b % a
        b = a
        a = r
    }
    return b
}