P3536 [POI2012]BON-Vouchers

    • 13通过
    • 38提交
  • 题目提供者洛谷OnlineJudge
  • 标签 数论,数学 POI 2012
  • 难度 普及+/提高
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    The candy shop owned by Byteasar sells delicious caramel candy.

    For every positive integer $c$ there is exactly one package that contains $c$ candies; currently no new deliveries are expected.

    To encourage customers to buy the sweets, Byteasar has planted $m$ vouchers for an annual supply of chocolate into some packages, making sure to put at most one voucher in each package.

    The carnival starts next week in Byteburg, and it will last $n$ days; on the $k$-th day of the carnival a party with $a_k$ guests will be held.

    Byteasar is confident that on the $k$-th day's morning each of those guests is going to buy, in his own store, the smallest package of candy available whose content can be equally distributed between the party guests. For example, if $n=2$, $a_1=4$, $a_2=2$, then on the first day of the carnival he expects to sell the packages containing four, eight, twelve, and sixteen candies, selling those with two and six candies on the second day.

    Now he is wondering which customers will end up with the packages holding the vouchers.

    He has asked you to write a program that will determine this for him.

    定义n个数为幸运数字,一共有n批人,设第i批人有x个,则它们会依次取走余下的x的倍数中最小的x个,问哪些人去走了幸运数字

    输入输出格式

    输入格式:

    On the first line of the standard input there is a single integer $m$ ($1\le m\le 1\ 000\ 000$) that denotes the number of vouchers.

    The $k$-th of the $m$ lines that follow holds an integer $b_k$ ($1\le b_k\le 1\ 000\ 000$)denoting the size (i.e., the number of candies inside) of a package in which Byteasar has placed the $k$-th voucher.

    These numbers are given in an increasing order.

    Then the next line contains a single integer $n$ ($1\le n\le 1\ 000\ 000$) that denotes the number of carnival days.

    The $k$-th of the $n$ lines that follow holds an integer $a_k$($1\le a_k\le 1\ 000\ 000$)denoting the number of guests attending the $k$-th party.

    You may assume that in tests worth at least 50% of the total points none of the numbers given on the input exceeds $5\ 000$.

    输出格式:

    In the first line of the standard output your program should print an integer $z$ - the number of packages with vouchers sold.

    The following $z$ lines should specify the numbers of those customers who bought a package with a voucher, in an increasing order.

    The customers are numbered from $1$ in the order of their purchases.

    输入输出样例

    输入样例#1: 复制
    4
    1
    6
    8
    16
    3
    4
    2
    4
    输出样例#1: 复制
    3
    2
    4
    6

    说明

    定义n个数为幸运数字,一共有n批人,设第i批人有x个,则它们会依次取走余下的x的倍数中最小的x个,问哪些人去走了幸运数字

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。