TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4384
  • Problem
  • P4384【SDOI2016】数字配对
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,128MB
    Description

    \(n\) 种数字,第 \(i\) 种数字是 \(a_i\)、有 \(b_i\) 个,权值是 \(c_i\)
    若两个数字 \(a_i\)\(a_j\) 满足,\(a_i\)\(a_j\) 的倍数,且 \(a_i / a_j\) 是一个质数,那么这两个数字可以配对,并获得 \(c_i \cdot c_j\) 的价值。
    一个数字只能参与一次配对,可以不参与配对。
    在获得的价值总和不小于 \(0\) 的前提下,求最多进行多少次配对。

    Input Format

    第一行一个整数 \(n\)
    第二行 \(n\) 个整数 \(a_1,a_2,\dots,a_n\)
    第三行 \(n\) 个整数 \(b_1,b_2,\dots,b_n\)
    第四行 \(n\) 个整数 \(c_1,c_2,\dots,c_n\)

    Output Format

    一行一个整数,表示最多进行多少次配对。

    Sample Input

    3
    2 4 8
    2 200 7
    -1 -2 1

    Sample Output

    4

    Hint

    样例输入

    3
    2 4 8
    2 200 7
    -1 -2 1
    

    样例输出

    4
    

    测试点 1 ~ 3:\(n \leq 10\)\(a_i \leq 10 ^ 9\)\(b_i = 1\)\(\left| c_i \right| \leq 10 ^ 5\)
    测试点 4 ~ 5:\(n \leq 200\)\(a_i \leq 10 ^ 9\)\(b_i \leq 10 ^ 5\)\(c_i = 0\)
    测试点 6 ~ 10:\(n \leq 200\)\(a_i \leq 10 ^ 9\)\(b_i \leq 10 ^ 5\)\(\left| c_i \right| \leq 10 ^ 5\)