Problem 2 is just finding the order of $$$a$$$ mod $$$p$$$. It can be done in $$$O(\sqrt{p})$$$ with the baby-step giant-step algorithm.

Problem 3 is NP-hard, but of course has a solution in O(nK). We reduce it to subset sum. If we want to know if some subset of $$$v_{1}, \dots, v_{n}$$$ has sum $$$k$$$, set $$$s = 1 + n \max v_{i}$$$, and make the numbers $$$a_{i} = v_{i} + s 2^{i} + s 2^{n}$$$, $$$a_{i + n} = s 2^{i} + s 2^{n}$$$. Now some subset of the integers $$$a_{1}, \dots, a_{2n}$$$ has sum $$$k + sn 2^{n} + s(2^{n} - 1)$$$ iff some subset of $$$v_{1}, \dots, v_{n}$$$ has sum $$$k$$$.

I can solve Problem 3 in $$$O(n^2*\min{a_i})$$$.

I don't know whether you know it.It is called "Congruence shortest-path problem".

We can find minimum value of $$$a$$$.Then build a graph which has $$$\min{a_i}$$$ nodes numbered from 0.

We can find that if there exist a solution satisfies $$$\sum_{i=1}^na_i*x_i=M$$$, there must be a solution satisfies $$$\sum_{i=1}^na_i*x'_i=M+\min{a}$$$.So the only question is to find the minimum value $$$L$$$ satisfies $$$L \equiv K$$$ ($$$\mod \min{a_i}$$$).

We add edges $$$(t,(t+a_i)\mod min{a},a_i)$$$ for each $$$i$$$.

If the shortest path between $$$0$$$ to $$$x$$$ equals to $$$val$$$, $$$val$$$ is the minimum value $$$L$$$ for remainder $$$x$$$.

So we can use SPFA Algorithm now.I don't know if it's $$$O(n*\min{a_i})$$$, but it's fast, that's enough.XD

Here is a classical problem.

can u provide link to the questions