BZOJ2118: 墨墨的等式(最短路 数论)

题意

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

Sol

maya神仙题啊,感觉自己做题难度跨度太大了qwq。

这里有一篇讲的非常好的博客https://blog.csdn.net/w4149/article/details/66476606?locationNum=3&fps=1

思路大概就是 利用取余的性质,把能够构造出来的解表示成统一的形式

发现该形式可以通过最短路更新

然后就做完了。。

#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<cstring>
#define lb(x) (x & (-x))
#define Pair pair<int, int> 
#define fi first
#define se second
#define MP(x, y) make_pair(x, y)
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 
    return x * f;
}
int N, vis[MAXN];
LL dis[MAXN], a[MAXN], Mi = 1e15, Bmin, Bmax;
void SPFA() {
    queue<int> q;
    memset(dis, 0xf, sizeof(dis));
    dis[0] = 0; vis[0] = 1, q.push(0);
    while(!q.empty()) {
        int p = q.front(); q.pop(); vis[p] = 1;
        for(int i = 1; i <= N; i++) {
            int to = (p + a[i]) % Mi;//tag
            if(dis[to] > dis[p] + a[i]) {
                dis[to] = dis[p] + a[i];
                if(!vis[to]) vis[to] = 1, q.push(to);
            }
        }
    }
}
LL Query(LL x) {
    LL rt = 0;
    for(int i = 0; i < Mi; i++) 
        if(dis[i] <= x) 
            rt += (x - dis[i]) / Mi + 1;
    return rt;
}
int main() {
    N = read(); Bmin = read(); Bmax = read();
    for(int i = 1; i <= N; i++) {
        a[i] = read();
        if(a[i] != 0) Mi = min(Mi, a[i]);
    }
    SPFA();
    printf("%lld", Query(Bmax) - Query(Bmin - 1));
    return 0;
}
/*

*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏图形学与OpenGL

机械版CG 实验4 裁剪

了解二维图形裁剪的原理(点的裁剪、直线的裁剪、多边形的裁剪),利用VC+OpenGL实现直线的裁剪算法。

1771
来自专栏chenssy

【死磕Java并发】-----J.U.C之ConcurrentHashMap红黑树转换分析

原文出处http://cmsblogs.com/ 『chenssy』 在【死磕Java并发】-----J.U.C之Java并发容器:ConcurrentHash...

3178
来自专栏数据结构与算法

cf550D. Regular Bridge(构造)

一篇写的非常好的博客:http://www.cnblogs.com/mangoyang/p/9302269.html

771
来自专栏Java架构沉思录

什么是一致性哈希算法

原文:http://www.cnblogs.com/hapjin/p/4737207.html

1261
来自专栏漫漫深度学习路

tensorflow自定义op:梯度

tensorflow自定义op,梯度 tensorflow 是 自动微分的,但是如果你不给它定义微分方程的话,它啥也干不了 在使用 tensorflow 的时...

7027
来自专栏chenjx85的技术专栏

leetcode-201-数字范围按位与

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

3662
来自专栏wOw的Android小站

[Tensorflow] 在Android运行TensorFlow模型

以下代码来自于TensorFlowObjectDetectionAPIModel.java

5781
来自专栏专知

【附源码】TensorFlow动态图(Eager模式)的那些神坑

导读:TensorFlow的动态图(Eager模式)为TensorFlow提供了Pythonic的API,让开发者可以像使用PyTorch一样使用TensorF...

972
来自专栏小樱的经验随笔

Lucas定理学习(进阶中)

(1)Lucas定理:p为素数,则有: ? ? ? (2)证明: n=(ak...a2,a1,a0)p = (ak...a2,a1)p*p + a0 =  [n...

2948
来自专栏我的博客

PHP取余的那些事

1、百分号取余 $val=9.45; $result=$val*100; echo intval($result); //这里输出944 echo $re...

37510

扫码关注云+社区

领取腾讯云代金券