P6156 Easy Problem

zbw ran into a problem. Since he is in a hurry to meet qby, he wants you to solve it for him.

Given $n, k$, find the value of the following expression: $\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k f(\gcd(i,j)) \gcd(i,j)$ Here, $\gcd(i,j)$ denotes the greatest common divisor of $i$ and $j$. The function $f$ is defined as follows: If $k$ has a square factor, then $f(k)=0$; otherwise, $f(k)=1$. **Update: Definition of a square factor. If there exists an integer $k(k>1)$ such that $k^2 \mid n$, then $k$ is a square factor of $n$.** **Output the answer modulo $998244353$.**

One line containing two integers $n, k$.

One line containing one integer, meaning the value of the answer modulo $998244353$.

| Test Point | $n$ | $k$ | | :----------: | :----------: | :----------: | | $1,2$ | $\leq10^3$ | $\leq10^3$ | | $3,4$ | $\leq2 \times 10^3$ | $\leq10^{18}$ | | $5 \sim8$ | $\leq5 \times 10^4$ | $\leq10^{18}$ | | $9$ | $\leq 5\times10^6$ | $=1$ | | $10,11$ | $\leq 5\times10^6$ | $=2$ | | $12,13$ | $\leq 5\times10^6$ | $\leq10^3$ | | $14 \sim20$ | $\leq 5\times10^6$ | $\leq10^{18}$ | For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^6$, $1 \leq k \leq 10^{18}$. **Update on 2020/3/16:** The time limit was changed to $1$s, ruling out solutions of $O(n\log k)$ and $O(n\log mod)$. Translated by ChatGPT 5