【同余最短路】P2371 [国家集训队] 墨墨的等式|省选-

发布于：2025-08-09 ⋅ 阅读:(16) ⋅ 点赞:(0)

本文涉及知识点

C++图论 最短路

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

题目描述

墨墨突然对等式很感兴趣，他正在研究 ∑ i = 1 n a i x i = b \sum_{i=1}^n a_ix_i=b ∑i=1n​ai​xi​=b 存在非负整数解的条件，他要求你编写一个程序，给定 n , a 1 … n , l , r n, a_{1\dots n}, l, r n,a1…n​,l,r，求出有多少 b ∈ [ l , r ] b\in[l,r] b∈[l,r] 可以使等式存在非负整数解。

输入格式

第一行三个整数 n , l , r n,l,r n,l,r。

第二行 n n n 个整数 a 1 … n a_{1\dots n} a1…n​。

输出格式

一行一个整数，表示有多少 b ∈ [ l , r ] b\in[l,r] b∈[l,r] 可以使等式存在非负整数解。

输入输出样例 #1

输入 #1

2 5 10
3 5

输出 #1

5

说明/提示

对于 20 % 20\% 20% 的数据， n ≤ 5 n \le 5 n≤5， r ≤ 10 r \le 10 r≤10。

对于 40 % 40\% 40% 的数据， n ≤ 10 n \le 10 n≤10， r ≤ 1 0 6 r \le 10^6 r≤106。

对于 100 % 100\% 100% 的数据， n ≤ 12 n \le 12 n≤12， 0 ≤ a i ≤ 5 × 1 0 5 0 \le a_i \le 5\times 10^5 0≤ai​≤5×105， 1 ≤ l ≤ r ≤ 1 0 12 1 \le l \le r \le 10^{12} 1≤l≤r≤1012。

同余最短路

简化版

令n =3,l = 0,r = 1 0 12 10^{12} 1012
式子一： a 0 × x 0 + a 1 × x 1 + a 1 × x 1 + a 2 × x 2 a_0\times x_0 +a_1\times x_1 +a_1\times x_1 + a_2 \times x_2 a0​×x0​+a1​×x1​+a1​×x1​+a2​×x2​。
式子二： a 1 × x 1 + a 2 × x 2 a_1\times x_1 + a_2 \times x_2 a1​×x1​+a2​×x2​
式子一二中, a i a_i ai​是已知值, x i x_i xi​是未知值。

性质一：如果 式子二 = = b 1 式子二==b1 式子二==b1存在自然数解，则 式子一 = = b 1 + z × a 0 ， z ∈ N 式子一==b1+ z \times a0，z \in \N 式子一==b1+z×a0，z∈N一定存在自然数解。
性质二：如果 式子二 = = b 1 式子二==b1 式子二==b1存在自然数解，且 b 1 < a 0 b1 < a0 b1<a0，或 式子二 = = b 1 − a 0 式子二==b1-a0 式子二==b1−a0无自然数解。则任何 y ≡ b 1 m o d    a 0 y \equiv b1 \mod a_0 y≡b1moda0​
{ 式子一 = = y 无自然数解 y < b 1 式子一 = = y 有自然数解 其它 \begin{cases} 式子一== y && 无自然数解 && y < b1 \\ 式子一==y && 有自然数解 && 其它 \\ \end{cases} {式子一==y式子一==y​​无自然数解有自然数解​​y<b1其它​

利用图论求b1

有向图G， ∀ i ∈ [ 0 , a 0 − 1 ] \forall i \in [0,a_0-1] ∀i∈[0,a0​−1],都有两条出边： i → ( i + a 1 ) m o d    a 0 , i → ( i + a 2 ) m o d    a 0 i \rightarrow (i+a_1)\mod a_0,i \rightarrow (i+a_2)\mod a_0 i→(i+a1​)moda0​,i→(i+a2​)moda0​。前者边权
a 1 a_1 a1​，后者边权 a 2 a_2 a2​。
性质三： 式子二 ≡ b m o d    a 0 式子二 \equiv b \mod a_0 式子二≡bmoda0​ 有正整数解    ⟺    \iff ⟺ 图G存在 0 → ( b m o d    a 0 ) 0 \rightarrow (b \mod a0) 0→(bmoda0)的路径。
充分性证明：令u是第i条边的u起点，前 x 1 x_1 x1​条边的终点 v = ( u + a 1 ) m o d    a 0 v=(u+a_1)\mod a_0 v=(u+a1​)moda0​，接着的 x 2 x_2 x2​条边 v = ( u + a 2 ) m o d    x 0 v=(u+a_2) \mod x0 v=(u+a2​)modx0。
必要性证明：如果存在合法路径则： x 1 = 边权 a 1 的边的数量 , x 2 = 边权 a 2 的边的数量 x1=边权a_1的边的数量,x2=边权a_2的边的数量 x1=边权a1​的边的数量,x2=边权a2​的边的数量。
结论： 式子二 ≡ i m o d    a 0 式子二 \equiv i \mod a_0 式子二≡imoda0​的最小式子二为 0 → i 0 \rightarrow i 0→i的最短路。

实现

a i a_i ai​升序排序，如果 a i = = 0 a_i==0 ai​==0删除。如果全部为0，则b只能是0。
按上述原理建边，求最短路。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T1, class T2, class T3, class T4,class T5 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4,T5>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t);
	return in;
}

template<class T1, class T2, class T3, class T4, class T5,class T6 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4, T5,T6>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >>get<5>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};

//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class  CHeapDis
{
public:
	CHeapDis(int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty)
	{
		m_vDis.assign(n, m_llEmpty);
	}
	void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
	{
		std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
		minHeap.emplace(0, start);
		while (minHeap.size())
		{
			const long long llDist = minHeap.top().first;
			const int iCur = minHeap.top().second;
			minHeap.pop();
			if (m_llEmpty != m_vDis[iCur])
			{
				continue;
			}
			m_vDis[iCur] = llDist;
			for (const auto& it : vNeiB[iCur])
			{
				minHeap.emplace(llDist + it.second, it.first);
			}
		}
	}
	vector<long long> m_vDis;
	const long long m_llEmpty;
};

class Solution {
public:
	long long Ans(vector<int>& as, long long left, long long r) {
		sort(as.begin(), as.end(), greater<>());
		as.erase(unique(as.begin(), as.end()), as.end());
		while (as.size() && (0 == as.back())) {
			as.pop_back();
		}
		if (as.empty()) { return 0; }
		const int M = as.back();
		vector < vector<pair<int, int>>> neiBo(M);
		for (int node = 0; node < M; node++) {
			for (const auto& w : as) {
				neiBo[node].emplace_back((node + w) % M, w);
			}
		}
		CHeapDis dis(M);
		dis.Cal(0, neiBo);
		long long ans = 0;
		auto f = [&](long long lr, long long bMin) {
			if (lr < bMin) { return 0LL; }
			return 1 + (lr - bMin) / M;
		};
		for (int i = 0; i < M; i++) {
			if (-1 == dis.m_vDis[i]) { continue; }
			ans += f(r, dis.m_vDis[i]);
			ans -= f(left - 1, dis.m_vDis[i]);
		}
		return ans;
	}
};
int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);	
	long long N,left,r;
	cin >> N >> left >> r ;	
	auto as = Read<int>(N);
#ifdef _DEBUG
	printf("left=%I64d,r=%I64d", left,r);
	Out(as, "as=");
	//Out(fun, ",fun=");
	//Out(que, ",que=");
#endif // DEBUG
	auto res = Solution().Ans(as,left,r);
	cout << res;
	return 0;
}

单元测试

long long left, r;
		vector<int> as;
		vector<tuple<int, int, int>> edge, vCloseInfo;
		TEST_METHOD(TestMethod11)
		{
			left = 5, r = 10,as = { 3,5 };
			auto res = Solution().Ans(as, left, r);
			AssertEx(5LL, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布