专栏首页数据结构与算法洛谷P2312 解方程(暴力)

洛谷P2312 解方程(暴力)

题意

题目链接

Sol

出这种题会被婊死的吧。。。

首先不难想到暴力判断,然后发现连读入都是个问题。

对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

#include<bits/stdc++.h>
#define Fin(x) {freopen(x, "r", stdin);}
#define int long long 
using namespace std;
const int MAXN = 2e5 + 10, mod = 19997;
inline int read() {
    char c = getchar(); int 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') % mod, c = getchar();
    return x * f;
}
int N, M, a[MAXN];
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    else return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int check(int val) {
    int now = 0;
    for(int i = N; i >= 0; i--) now = mul(now, val), now = add(now, a[i]);
    return now == 0;
}
signed main() {
    N = read(); M = read();
    for(int i = 0; i <= N; i++) a[i] = read();
    int ans = 0; vector<int> out;
    for(int i = 1; i <= M; i++) if(check(i)) ans++, out.push_back(i);
    printf("%d\n", ans);
    for(int i = 0; i < out.size(); i++) printf("%d\n", out[i]);
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10:Challenge 3(树状数组直接修改)

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

    attack
  • cf1037D. Valid BFS?(BFS?)

    可以这样想,在BFS序中较早出现的一定是先访问的,所以把每个点连出去的边按出现的前后顺序排个序

    attack
  • P1967 货车运输 未完成

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

    attack
  • 洛谷P5205 【模板】多项式开根(多项式sqrt)

    attack
  • 区间更新与点值

    用户2965768
  • 学生时代所学的一些 C 语言知识点回顾(1)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    耕耘实录
  • PTA刷题记录:L1-027 出租 (20分)

    一时间网上一片求救声,急问这个怎么破。其实这段代码很简单,index数组就是arr数组的下标,index[0]=2 对应 arr[2]=1,index[1]...

    英雄爱吃土豆片
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • 图论--拓扑排序--判断一个图能否被拓扑排序

    拓扑排序的实现条件,以及结合应用场景,我们都能得到拓扑排序适用于DAG图(Directed Acyclic Graph简称DAG)有向无环图, 根据关系我们能得...

    风骨散人Chiam
  • 使用高级程序设计语言实现集合的交并差运算

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券