ASSIEVE - A Simple Sieve
You are given a commutative associative unitary function \(x(i,j)\) defined over all \(0\le i,j,x(i,j)\lt 4\). In other words, this function satisfies, for all \(0\le i, j, k \lt 4\):
- \(x(i,j)=x(j,i)\)
- \(x(x(i, j), k)=x(i, x(j, k))\)
- \(x(0, i)=i\)
Define a function \(f(n)\) for all positive integers \(n\) such that:
- \(f(p^k)=(pk)\bmod 4\), that is, the remainder when \(pk\) is divided by 4
- If \(\gcd(a, b)=1\), then \(f(ab)=x(f(a),f (b))\)
Define:
$$g(n,k,r)=\sum_{i=1}^ni^k[f(i)=r]$$
where \([f(i)=r]\) is the Iverson bracket.
Given the function \(x\) and two integers \(m\), \(k\), for all integers \(1\le i\le\lfloor\sqrt n\rfloor\), calculate \(g(\lfloor\frac ni\rfloor, k, 0...3)\) modulo \(998\ 244\ 353\).
Input
The first line contains two integers \(m\) and \(k\). (\(1\le m\le 10^{10}\), \(0 \le k \le 1000\))
The following 4 lines contains 4 integers each. The i-th row j-th integer contains \(x(i-1,j-1)\).
Output
Output \(\lfloor\sqrt n\rfloor\) lines containing 4 integers each. The i-th row j-th integer contains \(g(\lfloor\frac ni\rfloor, k, j-1)\) modulo \(998244353\).
Example
Input:
10 0 0 1 2 3 1 2 3 0 2 3 0 1 3 0 1 2
Output:
2 2 3 3 2 1 1 1 1 0 1 1
Input:
100 100 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0
Output:
457599333 476580683 403589597 762762658 361221912 612412943 661908092 483645330 242804711 682542199 535167020 465246643 913280460 516845083 917292729 390364642 39265044 919790719 181416471 421087779 530140662 31014314 181416471 226287885 982924733 31014314 851084249 226287885 982924733 938693280 851084249 226287885 982924733 938693280 851084249 435036575 982924733 938693280 851084249 138976409
hide comments
Oleg:
2023-04-28 07:46:06
Nice one!
|
|
cubyte:
2022-10-25 07:37:09
P7572? |
Added by: | suffixautomata |
Date: | 2021-06-01 |
Time limit: | 7s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own |