Given $ n$ types of items with integer cost $ c_{i}$ (*there is an unlimited number of items of each type*), such that $ c_{i} \leq c$ for all $ i = 1, 2, \dots, n$ , answer (a lot of) queries of form “is there some set of items of total weight $ w$ ?” in time $ O(1)$ with some kind of precalculation in time $ O(n c \log c)$ .

I’ve got a hint – for every $ i = 0, 1, 2, \dots, c – 1$ find minimal $ x$ such that there is a set of items with total weight $ x$ and $ x \equiv i \quad (\bmod c)$ . How to calculate all $ x$ ‘s and how to use them to answer the queries?

This problem is somehow related to graphs and shortest paths, but I don’t understand the connection between actual knapsack-like thing and graphs (maybe there is some graph with paths of desired weight?).

Source: problem 76 on neerc.ifmo.ru wiki.