P2371 [国家集训队]墨墨的等式

题目描述

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

输入输出格式

输入格式：

输入的第一行包含3个正整数，分别表示NNN 、BMinB_{Min}BMin 、BMaxB_{Max}BMax 分别表示数列的长度、B的下界、B的上界。

输入的第二行包含N个整数，即数列{an}的值。

输出格式：

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

输入输出样例

输入样例#1：

2 5 10

3 5

输出样例#1：

说明

对于20%的数据，$N≤5N \le 5N≤5 ，1≤BMin≤BMax≤101 \le B_{Min} \le B_{Max} \le 101≤BMin≤BMax≤10 $。

对于40%的数据，$N≤10N \le 10N≤10 ，1≤BMin≤BMax≤1061 \le B_{Min} \le B_{Max} \le 10^61≤BMin≤BMax≤106 $。

对于100%的数据，$N≤12N \le 12N≤12 ，0≤ai≤5∗1050 \le a_i \le 5*10^50≤ai≤5∗105 ，1≤BMin≤BMax≤10121 \le B_{Min} \le B_{Max} \le 10^{12}1≤BMin≤BMax≤1012$ 。

题解

神题。

先做转化，求$[l,r]$内$B$的个数等价于$[0,r] - [0,l - 1]$的个数。

从$a$中找到一个最小的非零数$mi$,全部膜$mi$。

可以发现若$p$能被拼出，那么$p + mi$也能被拼出。

所有的答案$B$可以按照膜$p$的值分为$p$组，我们找到这$p$组里每一组最小的数即可推算其他数的个数（这些组在数论上叫剩余系）。

怎么求呢？

最短路！

对于每一个可能的$mod p$的余数建一个点，根据$a$的值连边，边权是对应$a$值。

注意空间和$long long$。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

inline long long max(long long a, long long b){return a > b ? a : b;}

inline long long min(long long a, long long b){return a < b ? a : b;}

inline void swap(long long &x, long long &y){long long  tmp = x;x = y;y = tmp;}

inline void read(long long &x)

{

    x = 0;char ch = getchar(), c = ch;

    while(ch < '0' || ch > '9') c = ch, ch = getchar();

    while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();

    if(c == '-') x = -x;

}

const long long INF = 0x3f3f3f3f3f3f3f3f;

struct Edge

{

	long long u,v,w,nxt;

	Edge(long long _u, long long _v, long long _w, long long _nxt){u = _u, v = _v, w = _w, nxt = _nxt;}

	Edge(){}

}edge[4000000];

long long head[500010], cnt;

inline void insert(long long a, long long b, long long c)

{

	edge[++ cnt] = Edge(a, b, c, head[a]), head[a] = cnt;

}

long long n, l, r, a[20], d[500010], vis[500010], mi, ans;

struct Node

{

	long long v, w;

	Node(long long _v, long long _w){v = _v, w = _w;}

};

struct cmp

{

	bool operator()(Node a, Node b){return a.w > b.w;}

};

std::priority_queue<Node, std::vector<Node>, cmp> q;

void dij()

{

	memset(d, 0x3f, sizeof(d)), d[1] = 0;

	q.push(Node(1, 0));

	while(q.size())

	{

		Node now = q.top();q.pop();

		if(vis[now.v]) continue; vis[now.v] = 1;

		for(long long pos = head[now.v];pos;pos = edge[pos].nxt)

		{

			long long v = edge[pos].v;

			if(vis[v]) continue;

			if(d[v] > d[now.v] + edge[pos].w)

				d[v] = d[now.v] + edge[pos].w, q.push(Node(v, d[v]));

		}

	}

}

int main()

{

	read(n), read(l), read(r), mi = INF;

	for(long long i = 1;i <= n;++ i) read(a[i]), mi = a[i] ? min(mi, a[i]) : mi;

	for(long long i = 1;i <= mi;++ i)

		for(long long j = 1;j <= n;++ j)

		{

			if(a[j] == 0) continue;

			insert(i, (i - 1 + a[j] + mi) % mi + 1, a[j]);

		}

	dij();

	for(long long i = 1;i <= mi;++ i)

	{

		if(r >= d[i]) ans += (r - d[i]) / mi + 1;

		if(l - 1>= d[i]) ans -= (l - 1 - d[i]) / mi + 1;

	}

	printf("%lld", ans);

 	return 0;

}

巴特西

洛谷P2371 [国家集训队]墨墨的等式