CF789B Masha and geometric depression

    • 9通过
    • 38提交
  • 题目来源 CodeForces 789B
  • 评测方式 RemoteJudge
  • 标签
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给你一个等比数列,首项为b1,公比为q,现在Masha在黑板上从首项开始书写这个等比数列,直到数列某项的绝对值大于l,给定m个整数,若该等比数列中的某项等同于这m个整数,则不会被写出。
    问Masha会写出多少个数字?如果她会写出无穷多个数字,输出inf
    注意: b1,q可能为0

    题目描述

    Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

    You are given geometric progression $ b $ defined by two integers $ b_{1} $ and $ q $ . Remind that a geometric progression is a sequence of integers $ b_{1},b_{2},b_{3},... $ , where for each $ i>1 $ the respective term satisfies the condition $ b_{i}=b_{i-1}·q $ , where $ q $ is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both $ b_{1} $ and $ q $ can equal $ 0 $ . Also, Dvastan gave Masha $ m $ "bad" integers $ a_{1},a_{2},...,a_{m} $ , and an integer $ l $ .

    Masha writes all progression terms one by one onto the board (including repetitive) while condition $ |b_{i}|<=l $ is satisfied ( $ |x| $ means absolute value of $ x $ ). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

    But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.

    输入输出格式

    输入格式:

    The first line of input contains four integers $ b_{1} $ , $ q $ , $ l $ , $ m $ (- $ 10^{9}<=b_{1},q<=10^{9} $ , $ 1<=l<=10^{9} $ , $ 1<=m<=10^{5} $ ) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

    The second line contains $ m $ distinct integers $ a_{1},a_{2},...,a_{m} $ (- $ 10^{9}<=a_{i}<=10^{9}) $ — numbers that will never be written on the board.

    输出格式:

    Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.

    输入输出样例

    输入样例#1: 复制
    3 2 30 4
    6 14 25 48
    
    输出样例#1: 复制
    3
    输入样例#2: 复制
    123 1 2143435 4
    123 11 -5453 141245
    
    输出样例#2: 复制
    0
    输入样例#3: 复制
    123 1 2143435 4
    54343 -13 6 124
    
    输出样例#3: 复制
    inf

    说明

    In the first sample case, Masha will write integers $ 3,12,24 $ . Progression term $ 6 $ will be skipped because it is a "bad" integer. Terms bigger than $ 24 $ won't be written because they exceed $ l $ by absolute value.

    In the second case, Masha won't write any number because all terms are equal $ 123 $ and this is a "bad" integer.

    In the third case, Masha will write infinitely integers $ 123 $ .

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