求a1x1+a2x2+a3x3+……+anxn = dy中的最小正整数解（是让y的值尽可能的小的正整数）
用图论方法最短路来做，从零点开始，记录d的剩余系中每个点已求得的多项式的最小值，最后0的情况整除d就是最优解（注意a=0的情况）
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<queue> #define ll long long using namespace std; ll n,d,dist[40005]; int vis[40005],flag = 0; ll a[40005]; void spfa(){ flag++; memset(dist,0,sizeof(dist)); queue<int> q; q.push(0); ll now,nxt,step; while(!q.empty()){ now = q.front(); q.pop(); vis[now] = 0; for(int i = 1;i <= n;i++){ if(a[i] == 0) continue; step = dist[now] + a[i]; nxt = now + a[i]; if(nxt >= d){ nxt %= d; } if(dist[nxt] > step || dist[nxt] == 0){ dist[nxt] = step; if(vis[nxt] != flag){ vis[nxt] = flag; q.push(nxt); } } } } } int main(){ freopen("math.in","r",stdin); freopen("math.out","w",stdout); while(scanf("%d%d",&n,&d)){ if(!n && !d) break; for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); } spfa(); if(!(dist[0]/d))cout<<1<<endl; else cout<<dist[0]/d<<endl; } return 0; }