AT_abc483_f.Sum of Mod of Linear

提高+/省选-

通过率:0%

时间限制:2.50s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given integers N,QN,Q and integer sequences A=(A1,A2,…,AN),B=(B1,B2,…,BN)A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) of length NN.

You are given QQ queries, so answer each of them. In each query, you are given an integer xx; find the value of ∑i=1N((x+Ai) mod Bi)\displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i).

给你整数 N,QN,Q 和长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)、B=(B1,B2,…,BN)B=(B_1,B_2,\ldots,B_N)。

你将收到 QQ 个查询,请对每个查询作答。对于每个查询,给定一个整数 xx;请计算 ∑i=1N((x+Ai) mod Bi)\displaystyle \sum_{i=1}^N ((x+A_i) \bmod B_i) 的值。

输入格式

The input is given from Standard Input in the following format:

NN
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
ANA_N BNB_N
QQ
query1\text{query}_1
query2\text{query}_2
⋮\vdots
queryQ\text{query}_Q

The ii-th query queryi\text{query}_i is given in the following format:

xx

输入从标准输入中按以下格式给出:

NN
A1A_1 B1B_1
A2A_2 B2B_2
⋮\vdots
ANA_N BNB_N
QQ
query1\text{query}_1
query2\text{query}_2
⋮\vdots
queryQ\text{query}_Q

第 ii 个查询 queryi\text{query}_i 的格式如下:

xx

输出格式

Print QQ lines.

The ii-th line (1≤i≤Q)(1\le i\le Q) should contain the answer to queryi\text{query}_i.

输出 QQ 行。

第 ii 行(1≤i≤Q1\le i\le Q)应包含 queryi\text{query}_i 的答案。

输入输出样例

  • 输入#1

    3
    1 3
    2 5
    0 1
    5
    0
    1
    2
    3
    200000

    输出#1

    3
    5
    4
    1
    2
  • 输入#2

    3
    2 3
    5 7
    0 9
    4
    9
    3
    6
    17

    输出#2

    2
    6
    12
    10
  • 输入#3

    8
    0 10
    3 8
    1 3
    5 7
    4 8
    4 9
    2 6
    5 7
    7
    130140
    70510
    22719
    104735
    119072
    127841
    191631

    输出#3

    16
    21
    31
    29
    19
    21
    27

说明/提示

Sample 1 Explanation:
The answer to each query is obtained as follows.

  • In the 11-st query, x=0x=0, so the answer is ((0+1) mod 3)+((0+2) mod 5)+((0+0) mod 1)=1+2+0=3((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3.
  • In the 22-nd query, x=1x=1, so the answer is ((1+1) mod 3)+((1+2) mod 5)+((1+0) mod 1)=2+3+0=5((1+1)\bmod 3)+((1+2)\bmod 5)+((1+0)\bmod 1)=2+3+0=5.
  • In the 33-rd query, x=2x=2, so the answer is ((2+1) mod 3)+((2+2) mod 5)+((2+0) mod 1)=0+4+0=4((2+1)\bmod 3)+((2+2)\bmod 5)+((2+0)\bmod 1)=0+4+0=4.
  • In the 44-th query, x=3x=3, so the answer is ((3+1) mod 3)+((3+2) mod 5)+((3+0) mod 1)=1+0+0=1((3+1)\bmod 3)+((3+2)\bmod 5)+((3+0)\bmod 1)=1+0+0=1.
  • In the 55-th query, x=200000x=200000, so the answer is ((200000+1) mod 3)+((200000+2) mod 5)+((200000+0) mod 1)=0+2+0=2((200000+1)\bmod 3)+((200000+2)\bmod 5)+((200000+0)\bmod 1)=0+2+0=2.

Constraints

  • 1≤N≤5×1051\le N\le 5\times 10^5
  • 0≤Ai<Bi≤5×1050\le A_i < B_i \le 5\times 10^5
  • 1≤Q≤2×1051\le Q\le 2\times 10^5
  • 0≤x≤5×1050\le x\le 5\times 10^5
  • All input values are integers.

样例 1 解释:
每个查询的答案计算方式如下:

  • 第 11 个查询中,x=0x=0,因此答案为 ((0+1) mod 3)+((0+2) mod 5)+((0+0) mod 1)=1+2+0=3((0+1)\bmod 3)+((0+2)\bmod 5)+((0+0)\bmod 1)=1+2+0=3。
  • 第 22 个查询中,x=1x=1,因此答案为 ((1+1) mod 3)+((1+2) mod 5)+((1+0) mod 1)=2+3+0=5((1+1)\bmod 3)+((1+2)\bmod 5)+((1+0)\bmod 1)=2+3+0=5。
  • 第 33 个查询中,x=2x=2,因此答案为 ((2+1) mod 3)+((2+2) mod 5)+((2+0) mod 1)=0+4+0=4((2+1)\bmod 3)+((2+2)\bmod 5)+((2+0)\bmod 1)=0+4+0=4。
  • 第 44 个查询中,x=3x=3,因此答案为 ((3+1) mod 3)+((3+2) mod 5)+((3+0) mod 1)=1+0+0=1((3+1)\bmod 3)+((3+2)\bmod 5)+((3+0)\bmod 1)=1+0+0=1。
  • 第 55 个查询中,x=200000x=200000,因此答案为 ((200000+1) mod 3)+((200000+2) mod 5)+((200000+0) mod 1)=0+2+0=2((200000+1)\bmod 3)+((200000+2)\bmod 5)+((200000+0)\bmod 1)=0+2+0=2。

约束条件

  • 1≤N≤5×1051\le N\le 5\times 10^5
  • 0≤Ai<Bi≤5×1050\le A_i < B_i \le 5\times 10^5
  • 1≤Q≤2×1051\le Q\le 2\times 10^5
  • 0≤x≤5×1050\le x\le 5\times 10^5
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页