AT_abc483_f.Sum of Mod of Linear
提高+/省选-
通过率:0%
时间限制:2.50s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given integers N,Q and integer sequences A=(A1,A2,…,AN),B=(B1,B2,…,BN) of length N.
You are given Q queries, so answer each of them. In each query, you are given an integer x; find the value of i=1∑N((x+Ai)modBi).
给你整数 N,Q 和长度为 N 的整数序列 A=(A1,A2,…,AN)、B=(B1,B2,…,BN)。
你将收到 Q 个查询,请对每个查询作答。对于每个查询,给定一个整数 x;请计算 i=1∑N((x+Ai)modBi) 的值。
输入格式
The input is given from Standard Input in the following format:
N
A1 B1
A2 B2
⋮
AN BN
Q
query1
query2
⋮
queryQ
The i-th query queryi is given in the following format:
x
输入从标准输入中按以下格式给出:
N
A1 B1
A2 B2
⋮
AN BN
Q
query1
query2
⋮
queryQ
第 i 个查询 queryi 的格式如下:
x
输出格式
Print Q lines.
The i-th line (1≤i≤Q) should contain the answer to queryi.
输出 Q 行。
第 i 行(1≤i≤Q)应包含 queryi 的答案。
输入输出样例
输入#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 1-st query, x=0, so the answer is ((0+1)mod3)+((0+2)mod5)+((0+0)mod1)=1+2+0=3.
- In the 2-nd query, x=1, so the answer is ((1+1)mod3)+((1+2)mod5)+((1+0)mod1)=2+3+0=5.
- In the 3-rd query, x=2, so the answer is ((2+1)mod3)+((2+2)mod5)+((2+0)mod1)=0+4+0=4.
- In the 4-th query, x=3, so the answer is ((3+1)mod3)+((3+2)mod5)+((3+0)mod1)=1+0+0=1.
- In the 5-th query, x=200000, so the answer is ((200000+1)mod3)+((200000+2)mod5)+((200000+0)mod1)=0+2+0=2.
Constraints
- 1≤N≤5×105
- 0≤Ai<Bi≤5×105
- 1≤Q≤2×105
- 0≤x≤5×105
- All input values are integers.
样例 1 解释:
每个查询的答案计算方式如下:
- 第 1 个查询中,x=0,因此答案为 ((0+1)mod3)+((0+2)mod5)+((0+0)mod1)=1+2+0=3。
- 第 2 个查询中,x=1,因此答案为 ((1+1)mod3)+((1+2)mod5)+((1+0)mod1)=2+3+0=5。
- 第 3 个查询中,x=2,因此答案为 ((2+1)mod3)+((2+2)mod5)+((2+0)mod1)=0+4+0=4。
- 第 4 个查询中,x=3,因此答案为 ((3+1)mod3)+((3+2)mod5)+((3+0)mod1)=1+0+0=1。
- 第 5 个查询中,x=200000,因此答案为 ((200000+1)mod3)+((200000+2)mod5)+((200000+0)mod1)=0+2+0=2。
约束条件
- 1≤N≤5×105
- 0≤Ai<Bi≤5×105
- 1≤Q≤2×105
- 0≤x≤5×105
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?