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

    给出n个整数A1,A2,A3,...,An,然后有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 (1 ≤ n ≤ 10^5)
    第二行,n个整数,表示A1,A2,...,An (2 ≤ Ai ≤ 10^7)
    第三行,一个整数m (1 ≤ m ≤ 10000)
    接下来m行,每行两个整数L,R表示一次询问 (2 ≤ L≤ R ≤ 2*10^9)

    输出格式

    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


    来源  codeforces 385C