### learningcurve_'s blog

By learningcurve_, history, 5 weeks ago,

I tried to think of ways to solve this problem, after not being able to think of a solution which I could reason about, I read the editorial and understood the binary search solution, but I don't understand why the greedy solution works.

Could someone help reason about the greedy solution?

• +1

By learningcurve_, 7 weeks ago,

Yesterday I read in cpalgorithm that if we are given a prime modulus, $p$, which is of the form $p = c \cdot 2^{k} + 1$, then, assuming $g$ is a primitive root of the prime $p$, then, exponentiating $g$, we can obtain congruences of numbers comprime to $p$, $g^{k} \equiv a \pmod{p}$ where $gcd(a, m) = 1$. As, this $g$ produces congruences of all numbers less than $p$ which are coprime to $p$, it obviously has $z$, such that $g^{z} \equiv 1 \pmod{p}$, $z = \varphi(p) = c \cdot 2^{k}$. If $c = 1$, then, if $\omega_{2^{k}}$ is the $2^{k}$-th root of unity modulo $p$. we can use $(\omega_{2^{k}}^{2})^{2^{k - 1}} = \omega_{2^{k}}^{2^{k}} = 1$ which means $\omega_{2^{k}}^{2} = \omega_{2^{k - 1}}$ and we can obtain answer. If $c \neq 1$, $c \equiv 1 \pmod{p}$ and you had two polynomials, both of degree $n$ where $n$ is a power of 2, $2n \leq 2^{k}$ and you wanted to get the convolution of the two polynomials, how would you do it? Or if there is some other way, please do share.

If I have said anything wrong, please correct me.

UPD: After reading again, I realize that $g^{c}$ is the $2^{k}$th root of unity as the period is $c \cdot 2^{k}$ ending with $1$, Sorry for asking this stupid question.

• +21