「PFLOI R1」PFL 除法

Luogu

IDLGP9589

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP洛谷原创O2优化

花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作： + 选择两个整数 $i$ 和 $j$，满足 $1\le i\le n$，$1\le j\le m$ 且 $B_j \mid A_i$，然后将 $A_i$ 变为 $\frac{A_i}{B_j}$。 **注意**：$A$ 和 $B$ 中的每个元素都可以选择并被**操作多次**。最终要使得 $A$ 中的元素都相等，请求出最少的操作次数；若无解，输出 `-1`。 ## Input 第一行两个正整数 $n$ 和 $m$。第二行 $n$ 个正整数表示序列 $A$。第三行 $m$ 个正整数表示序列 $B$。 ## Output 输出一个整数表示最少的操作次数；若无解，输出 `-1`。 [samples] ## Background [有必要把所有比赛题的背景连在一起](https://www.luogu.com.cn/paste/enzfvjum)。就这样，新世界的大门向它们敞开了…… “喵！”一只可爱的花猫向它们问好。 “你们刚来到这？” “嗯。” “我带你们去转转吧，谁叫我这么可爱呢！” “……” 花猫突然止住，打量一番手中的序列，俶尔又微笑着说： “但你们要先答出我的问题哦。” ## Note **本题采用捆绑测试**。 | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :-----:| | $1$ | $A$ 中所有元素相等 | $5$ | | $2$ | $n=2$ | $15$ | | $3$ | $n,m\le10^3$ | $20$ | | $4$ | $n,m\le10^4$ | $20$ | | $5$ | 无 | $40$ | 对于所有数据，$1\le n,m\le5\times10^5$，$1\le A_i,B_i\le5\times10^5$。

Samples

Input #1

4 5
16 24 28 36
11 4 7 3 2

Output #1

Input #2

2 3
11 13
13 1 11

Output #2

Input #3

2 2
2 3
4 5

Output #3

-1

API Response (JSON)

{
  "problem": {
    "name": "「PFLOI R1」PFL 除法",
    "description": {
      "content": "花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作： + 选择两个整数 $i$ 和 $j$，满足 $1\\le i\\le n$，$1\\le j\\le m$ 且 $B_j \\mid A_i$，然后将 $A_i$ 变为 $\\frac{A_i}{B_j}$。 **注意**：$A$ 和 $B$ 中的每个元素都可以选择并被**操作多次**。 最终要",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9589"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作：\n\n+ 选择两个整数 $i$ 和 $j$，满足 $1\\le i\\le n$，$1\\le j\\le m$ 且 $B_j \\mid A_i$，然后将 $A_i$ 变为 $\\frac{A_i}{B_j}$。\n\n**注意**：$A$ 和 $B$ 中的每个元素都可以选择并被**操作多次**。\n\n最终要...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments