We study dense instances of optimization problems with variables taking values in Z _p. Specifically, we study systems of functions from Z ^k _p to Z ^p where the objective is to make as many functions as possible attain the value zero. We generalize earlier sampling methods and thereby construct a randomized polynomial time approximation scheme for instances with θ(n ^k) functions where n is the number of variables occurring in the functions.