No.1575 Divisor Function Hard
タグ : / 解いたユーザー数 4
作問者 :
PCTprobability
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もしくは右上の雲マークをクリックしてアカウントを作成してください。