I was trying to solve this problem QTDIVIDE on spoj and I think it is a DP problem but couldn't solve it. Can someone help me out and point me into the right direction?

Thanks in advance!