如题,Substak#1 一直是RE 没想明白为什么,也没发现有哪里会溢出的 求大佬解惑
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace::std;
long long INF = 1ull<<63-1;
int main() {
int n;
long long l, r ,a;
cin >> n >> l >> r;
vector<int> A;
for (int i = 0; i < n; i++)
{
cin >> a;
A.push_back(a);
}
sort(A.begin(), A.end());
vector<long long> dis(A[0],INF);
dis[0] = 0;
bool flag = true;
queue<int> q;
q.push(0);
vector<int>vis(A[0], 0);
vis[0] = 1;
int cur;
while (!q.empty())
{
cur = q.front();
q.pop(), vis[cur] = 0;
for (int j = 1; j < A.size(); j++)
{
if (dis[(cur + A[j]) % A[0]] > dis[cur] + A[j])
{
dis[(cur + A[j]) % A[0]] = dis[cur] + A[j];
if (!vis[(cur + A[j]) % A[0]])
{
vis[(cur + A[j]) % A[0]] = 1;
q.push((cur + A[j]) % A[0]);
}
}
}
}
//while (flag)
//{
// flag = false;
// for (int i = 0; i < dis.size(); i++)
// {
// if (dis[i] == INF)
// continue;
// for (int j = 1; j < A.size(); j++)
// {
// if (dis[(i + A[j]) % A[0]] > dis[i] + A[j])
// {
// dis[(i + A[j]) % A[0]] = dis[i] + A[j];
// flag = true;
// }
// }
// }
//}
long long ans=0;
for (int d = 0;d <dis.size();d++)
{
if (dis[d] == INF)
continue;
if (dis[d] < l)
{
long long L = (l-d-1) / A[0] * A[0] +d;
ans += (r - L) / A[0];
}
else if (dis[d] >= l&& dis[d] <=r)
ans += (r - dis[d]) / A[0] + 1;
}
cout << ans;
}