Rozwiązanie będzie zastosowanie algorytmu plecakowego z drobnymi modyfikacjami (opisany jest tu jeden przypadek jego wykorzystania, po więcej odsyłam do internetu)
Gwaizdki w nawiasach (*) oznaczają porady implementacyjne. Radzę je dopiero przeczytać po zrozumieniu działania algorytmu.
Rozwiązanie opiera się na programowaniu dynamicznym (tak jak i cały plecak). Będziemy patrzeć jakie reszty z dzielenia przez dzielnik możemy uzyskać po wybraniu jednej, dwóch, trzech ... wszystkich liczb. W tym celu deklarujemy sobie tablicę dwuwymiarową o wielkości: liczba liczb w ciągu * dzielnik (*). Na początku ma ona same zera i będziemy wstawiać jedynki w miejsca do których możemy dojść wystawiając znaki między liczby w ciągu. Pierwszy wymiar będzie oznaczał którą liczbę w ciągu rozpatrujemy, a drugi sumę dotychczas wybranych liczb.
Na początku wstawiamy 1 w miejscu [0][0]. Nie wybierając żadnej liczby (pierwsze 0) możemy otrzymać resztę 0 (drugie 0). (Tego co właśnie napisałem nie trzeba pisać w kodzie, ma to jedynie pomóc w zrozumieniu algorytmu). Teraz bierzemy pierwszą liczbę. Niech ma ona wartość a. Nie możemy wstawić przed nią minusa, więc wstawiamy 1 w miejsce [1][a].
I teraz właściwa część algorytmu. Bierzemy po kolei liczby. Niech aktualnie rozpatrywana liczba będzie na b-tym miejscu w ciągu i ma wartość c. Żeby sprawdzić jakie wartości możemy uzyskać po dostawieniu tej liczby musimy przejść się po całym rzędzie [b-1][od 1 do k] (***) . Za każdym razem gdy znajdziemy (załóżmy że znalazłem w miejscu [b-1][d]) to możemy wstawić 1 w miejsca [b][d - c] oraz [b][d + c] (**) . Otrzymamy to po wystawieniu - i + przed rozpatrywaną liczbą do wcześniej otrzymanego ciągu.
Na końcu jeżeli w miejscu [n] [K] jest 1 to ciąg jest podzielny. Pamiętaj o czyszczeniu tablicy przed każdym testem.
Porady implementacyjne
Bez gwiazdki - warto zmodulować każdą liczbę ciągu przez dzielnik
(*) polecam powiększyć o 5 oba wymiary na wszelki wypadek, aby nie okazało się, że przypadkiem wyjdziemy poza tablicę
(**) WAŻNE - może się okazać, że d - c < 0 lub d+c>k. Wtedy trzeba zmodulować przez k. Niestety w c++ modulowanie liczb ujemnych nie działa tak jak w matematyce dlatego przed zmodulowaniem d-c trzeba dodać dzielnik.
(***) możesz rozpatrywać przedział od 1 do k lub od 0 do k-1, nie ma to w zasadzie znaczenia. Pamiętaj tylko aby w dobrym miejscu sprawdzić wynik.
PS: zadanie można zrobić w mniejszej złożoności pamięciowej, ale wolałem opisać prostszą wersję