問題一覧 > 通常問題

No.1575 Divisor Function Hard

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : PCTprobability
お気に入りにしたユーザー ProblemId : 6345 / 自分の提出
問題文最終更新日: 2026-10-25 12:20:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Note

The time limit for this problem is $5$ sec. The writer's solution (C++) runs in $1567$ ms.

Problem Statement

For positive integers $x,y$, define $f_{u,v}(x,y)=\displaystyle \sum_{i|x\ \land\ 1 \le i \le y}^{} (ux+vi)^P$.

That is, $f_{u,v}(x,y)$ is the sum of $(ux+vi)^P$ over all divisors $i$ of $x$ that are at least $1$ and at most $y$.


You are given sequences of positive integers $A_1,A_2,\dots,A_N$, $B_1,B_2,\dots,B_M$, and $C_1,C_2,\dots,C_K$.

You are also given a sequence of positive integers $U_1,U_2,\dots,U_Q$. For each $q$ between $1$ and $Q$, inclusive, solve the following problem.

There are $NMK$ ways to choose $1$ element from each of $A,B,C$. For all of these ways, compute $\displaystyle \sum_{p=1}^{U_q} f_{B_j,C_k}(p,A_i)$, and output the sum of these values modulo $998244353$.

Input

$N\ M\ K\ P\ Q$
$A_1\ A_2\ \dots\ A_N$
$B_1\ B_2\ \dots\ B_M$
$C_1\ C_2\ \dots\ C_K$
$U_1\ U_2\ \dots\ U_Q$

  • All input values are integers.
  • $1 \le N,M,K,P,Q \le 10^5$
  • $1 \le A_i,U_q \le 10^5$
  • $1 \le B_j,C_k \le 10^9$

Output

Output $Q$ lines. On line $q$, output the sum of $\displaystyle \sum_{p=1}^{U_q} f_{B_j,C_k}(p,A_i)$ modulo $998244353$.

Sample

Sample 1
Input
1 1 1 2 1
3
2
3
4
Output
797

$f_{2,3}(1,3)=(2 \times 1+3\times 1)^2=25$

$f_{2,3}(2,3)=(2 \times 2+3\times 1)^2+(2\times 2+3 \times 2)^2=149$

$f_{2,3}(3,3)=(2 \times 3+3\times 1)^2+(2\times 3+3\times 3)^2=306$

$f_{2,3}(4,3)=(2 \times 4+3\times 1)^2+(2 \times 4+3 \times 2)^2=317$

Therefore, output $25+149+306+317=797$.

Sample 2
Input
3 4 5 10 6
4 10 14
5 6 38 7
29 38 65 2 8
2 5 4 6 7 9
Output
150320443
328973193
391678442
549317104
634739291
657656843

Sample 3
Input
12 8 9 4563 8
576 4837 995 2837 2 3948 69479 79683 12 38457 34 27574
23765 38573 34 8785 47 3881 1201 3009
185 3821 48486 69770 382 18 1 45 5677
10 20 30 40 50 60 100 1000
Output
327615460
711805763
554598826
435287792
146352218
554366329
470855435
188196334

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。