国家集训队墨墨的等式

wjh15101051's space

卧薪尝胆，厚积薄发。

国家集训队墨墨的等式

Date: Fri Sep 07 19:44:55 CST 2018

In Category: NoCategory

Description：

对于方程 $a_1x_1+a_2x_2+…+a_nx_n=B$ ，给定 $N$ 、 $a_i$ 、以及 $B$ 的取值范围，求出有多少 $B$ 可以使等式存在非负整数解。

$1\le n \le 12,1\le a_i\le 5\times 10^5$

Solution：

注意到如果 $b$ 是一个符合条件的 $B$ ，那么 $b+a_1$ 也符合条件，于是取最小的 $a$ 做 $a_1$ ，然后同余类最短路就行了。最后统计答案有点恶心。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

typedef long long ll;

ll bmax,bmin;

int n;

#define MAXN 14

ll a[MAXN];

#define MAXK 500010

struct edge

{

	int to,nxt;

	ll v;

}e[MAXN * MAXK];

int edgenum = 0;

int lin[MAXK] = {0};

void add(int a,int b,ll c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

ll d[MAXK];

bool v[MAXK];

int main()

{

	scanf("%d%lld%lld",&n,&bmin,&bmax);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	sort(a + 1,a + 1 + n);

	for(int i = 2;i <= n;++i)

		for(int k = 0;k < a[1];++k)

			add(k,(k + a[i]) % a[1],a[i]);

	priority_queue< pair<ll,int> > q;

	q.push(make_pair(0,0));

	memset(d,0x3f,sizeof(d));

	d[0] = 0;

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	ll ans = 0;

	for(int i = 0;i < a[1];++i)

	{

		int l,r;

		if(d[i] > bmax)r = 0;

		else r = (bmax - d[i]) / a[1] + 1;

		if(d[i] > bmin - 1)l = 0;

		else l = (bmin - 1 - d[i]) / a[1] + 1;

		ans += r - l;

	}

	cout << ans << endl;

	return 0;

}

In tag: 图论-同余类最短路

wjh15101051