TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3715
  • 题目
  • P3715蒲公英的约定
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 时限1000ms
    问题描述

    Description

    wy和wjk是好朋友。

    今天他们在一起聊天,突然聊到了以前一起唱过的《蒲公英的约定》。

    “说到蒲公英,我给你讲一个故事吧。”

    “嗯?”

    “从前有两朵蒲公英,他们约定一起长大,在N天内每一天都长出同样多的种子,可是,他们不想让其他植物知道他们到底要长出多少种子,于是他们中的哥哥想出了一个办法,最开始,他会告诉弟弟一个数P,然后在接下来的若干天里每一天哥哥会告诉弟弟两个数:a,c,然后弟弟在这一天会干如下几件事情:

    Step 1:首先把c和lastans按位异或得到b,最开始lastans是0

    Step 2:如果这天的b等于0,则说明他们已经长出了所有要长出的种子,哥哥与弟弟的交流结束(输入文件也到此结束)

    Step 3:如果这天的b不等于0,弟弟会求出一个最小的非负整数x使得ax≡b Mod P(即ax除以P的余数是b),[题目保证可以找到这样的x]

    Step 4:lastans赋值为x

    现在给你哥哥给弟弟的所有数字,你能求出每天弟弟要长出的种子的数量(即每天的x)吗”

    “唔。。。”

    [简化版题目描述]

    Description

    输入格式

    第一行一个整数P

    接下来若干行(不妨认为有N+1行),每行两个整数a,c,含义如题目描述所示。

    输出格式

    一共N行,每行一个整数,第i行代表第i天弟弟要长出的种子的数量(即第i天的x的值)

    [第N+1天弟弟会在第二步停止,所以不用求出这一天的x输出,只作为输入文件结束的标志]

    样例输入 1

    17
    2 8
    8 11
    5 5
    4 12

    样例输出 1

    3
    1
    12

    样例输入 2

    13
    5 5
    7 8
    9 5
    6 1
    5 0

    样例输出 2

    1
    4
    0
    0

    提示

    【样例解释(第一个样例)】

    [以下N行,每行两个整数,第一个整数代表第i天的a,第二个整数代表第i天的b]

    2 8

    8 8

    5 4

    4 0

    【数据范围】

    对于30%的数据 1 ≤ N ≤ 1000 1 ≤ P ≤ 1000

    对于60%的数据 1 ≤ N ≤ 10000 1 ≤ P ≤ 60000

    另有10%的数据 每一天的a都相等

    对于100%的数据 1 ≤ N ≤ 100000 1 ≤ P ≤ 100000 且P是素数 a,b ≤ P-1


    来源  ShadowIterator原创