問題一覧 > 通常問題

No.1575 Divisor Function Hard

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 4
作問者 : PCTprobabilityPCTprobability
0 ProblemId : 6345 / 自分の提出
問題文最終更新日: 2021-08-01 18:07:52

注意

この問題のTLは $5$ sec です。Writer解(C++)の実行時間は $1567$ ms です。

問題文

正整数 $x,y$ に対し、$f_{u,v}(x,y)=\displaystyle \sum_{i|x\ \land\ 1 \le i \le y}^{} (ux+vi)^P$ と定義します。

つまり、$f_{u,v}(x,y)$ は $x$ の約数のうち、$1$ 以上 $y$ 以下である全ての整数 $i$ に対する $(ux+vi)^P$ の総和です。


正整数列 $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$ が与えられるので、$1$ 以上 $Q$ 以下の各 $q$ に対して以下の問題に答えてください。

$A,B,C$ から要素を $1$ 個ずつ選ぶ方法は $NMK$ 通りありますが、その全てに対して $\displaystyle \sum_{p=1}^{U_q} f_{B_j,C_k}(p,A_i)$ を求め、その総和を $998244353$ で割った余りを出力してください。

入力

$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$

  • 入力は全て整数である。
  • $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$

出力

$\displaystyle \sum_{p=1}^{U} f_{A_i,B_j}(p,C_k)$ の総和を $998244353$ で割った余りを出力してください。

サンプル

サンプル1
入力
1 1 1 2 1
3
2
3
4
出力
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$

より、$25+149+306+317=797$ を出力してください。

サンプル2
入力
3 4 5 10 6
4 10 14
5 6 38 7
29 38 65 2 8
2 5 4 6 7 9
出力
150320443
328973193
391678442
549317104
634739291
657656843

サンプル3
入力
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
出力
327615460
711805763
554598826
435287792
146352218
554366329
470855435
188196334

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