bzoj2118

2118: 墨墨的等式

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 2390 Solved: 937
[Submit][Status][Discuss]

Description

墨墨突然对等式很感兴趣，他正在研究a1x1+a2x2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

Input

输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数，即数列{an}的值。

Output

输出一个整数，表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10
3 5

Sample Output

HINT

对于100%的数据，N≤12，0≤ai≤5*10^5，1≤BMin≤BMax≤10^12。

分析

我们发现这已经不是简单的数论题了！（我开始并没有发现）对于这种无限取的背包问题，可以转化为取mod最短路的问题。具体怎么想呢？

首先我们将a排序（因为这道题n比较小其实可以不用但是这样更优秀）考虑对于a1，对于所有能够取到的数x，都有x+a1*k（k任意）一定会被取到。所以我们就可以把所有能够取到的数%a1，发现结果属于0~a1-1中的一个，那么我们就把每一个0~a1看做一个集合包括所有能够取到的数%a1=该值。

那么最小路怎么解释呢？相当于每次加一个数就走了一条边，我们将所有<r的数%a1的最小值看做最短路，求完后遍历0~a1分别求r和l-1的组合的个数（前缀和）减去即可。

这里我用dijkstra。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<ctype.h>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<queue>
 7 #include<utility>
 8 #include<vector>
 9 #include<functional>
10 using namespace std;
11 const int maxn=5e5+5;
12 typedef long long ll;
13 typedef pair<ll,int> pairr;
14 
15 int n,a[15];
16 ll L, R;
17 
18 struct Edge{
19     int to,nxt,dis;
20 }e[maxn*10];
21 
22 int  head[maxn];int ecnt;
23 
24 inline void addedge(int  from,int to,int dis)
25 {
26     e[++ecnt]=(Edge){to,head[from],dis},head[from]=ecnt;
27 }
28 
29 ll dis[maxn];
30 bool vis[maxn];
31 void dijkstra()
32 {
33     priority_queue <pairr,vector<pairr >,greater<pairr > >q;
34     for(int i=0;i<a[1];i++)dis[i]=(ll)1e60;
35     dis[0]=0;
36     q.push(make_pair(0,0));
37     while(!q.empty())
38     {
39         int v=q.top().second;q.pop();
40         if(vis[v])continue;vis[v]=1;
41         for(int i=head[v];i!=-1;i=e[i].nxt)
42         {
43             int u=e[i].to;
44             ll w=(ll)e[i].dis;
45             if(dis[u]>dis[v]+w)
46             {
47                 dis[u]=dis[v]+w;
48                 q.push(make_pair(dis[u],u));
49             }
50         }
51     }
52 }
53 
54 inline ll getans(ll x)
55 {
56     ll ans=0;
57     for(int i=0;i<a[1];i++)
58         if(dis[i]<=R){
59             ll zp=max(0ll,(x-dis[i])/a[1]);
60             if(zp*a[1]+dis[i]<x)ans++;
61             ans+=zp;
62         }
63     return ans;
64 }
65 
66 int main()
67 {
68     scanf("%d%lld%lld",&n,&L,&R);
69     memset(head,-1,sizeof(head));
70     for(int i=1;i<=n;i++)
71     {
72         scanf("%d",&a[i]);
73         if(a[i]==0)n--,i--;
74     }
75     sort(a+1,a+1+n);
76     for(int i=0;i<a[1];i++)
77         for(int j=2;j<=n;j++)
78         addedge(i,(a[j]+i)%a[1],a[j]);
79     dijkstra();
80 //    printf("%lld\n",getans(R)-getans(L-1)+1);
81     ll ans=0;
82     for (int i=0;i<a[1];i++) if (dis[i]<=R) {
83         ll l=max(0ll,(L-dis[i])/a[1]);
84         if (l*a[1]+dis[i]<L) l++;
85         ll r=(R-dis[i])/a[1];
86         if (r*a[1]+dis[i]>R) r--;
87         ans+=r-l+1;
88     }
89     printf("%lld\n",ans);
90     return 0;
91 }

PS调了几天竟然是板子写错了！！！淦