TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P4490
  • 题目
  • P4490素数的个数
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 时限2s,空间限制512m
    问题描述

    何老板给出n个整数 \(A_1,A_2,A_3,...,A_n\) ,然后向你提出m次询问,每次询问形如 \([L,R]\) ,问A数列中的数字能被位于区间 \([L,R]\) 中的素数整除多少次?

    比如:

    \(A\) 数列为:\(5 , 5 , 7 , 10 , 14 , 15\)

    询问 \([L,R]=[2,11]\),该区间中的素数有$ 2,3,5,7,11 $
    对于素数 \(2\)\(A\) 数列的 \(10,14\) 能被 \(2\) 整除,整除次数 \(+2\)
    对于素数 \(3,A\) 数列的 \(15\) 能被 \(3\) 整除,整数次数 \(+1\)
    对于素数 \(5,A\) 数列的 \(5,5,10,15\) 能被 \(5\) 整除,整除次数 \(+4\)
    对于素数 \(7,A\) 数列的 \(7,14\) 能被 \(7\) 整除,整除次数 \(+2\)
    对于素数 \(11,A\) 数列中没有数字能被它整数,整除次数 \(+0\)
    因此答案为 \(9\)

    输入格式

    第一行,一个整数 \(n\)
    第二行,\(n\) 个整数,表示$ A_1,A_2,...,A_n $
    第三行,一个整数$m$
    接下来 \(m\) 行,每行两个整数 \(L,R\) 表示一次询问

    输出格式

    \(m\) 行,每行一个整数,表示对应询问的结果

    样例输入 1

    6
    5 5 7 10 14 15
    3
    2 11
    3 12
    4 4

    样例输出 1

    9
    7
    0

    样例输入 2

    7
    2 3 5 7 11 4 8
    2
    8 10
    2 123

    样例输出 2

    0
    7

    样例输入 3

    9
    9999991 9999943 9999883 4658161 4657997 2315407 2315263 1000003 1000033
    13
    9999991 9999991
    9999943 9999943
    9999883 9999883
    4658161 4658161
    4657997 4657997
    2315407 2315407
    2315263 2315263
    1000003 1000003
    1000033 1000033
    2 2000000000
    2000000000 2000000000
    9999992 2000000000
    1000033 9999990

    样例输出 3

    1
    1
    1
    1
    1
    1
    1
    1
    1
    9
    0
    0
    7

    提示

    \(1 ≤ n ≤ 10^5\)
    \(2 ≤ Ai ≤ 10^7\)
    \(1 ≤ m ≤ 10000\)
    \(2 ≤ L≤ R ≤ 2*10^9\)


    来源  codeforces 385C