luogu题解P2312解方程--暴力膜+秦九韶

题目链接

https://www.luogu.org/problemnew/show/P2312

分析

这道题很毒啊,这么大的数。

但是如果多项式$\sum_{i=0}^N a[i]X^i=0$则$\sum_{i=0}^N a[i]X^i \mod P=0$

于是我们可以暴力膜一模，然后在$[1,m]$中枚举就好了。但是呢，万一这个多项式的值是$P$的倍数,也会变成0，所以保险起见搞几个又大又质的数膜一膜就好了。

但是$Exciting$的是呢,我在洛谷上开O2能过，而BZOJ就不那么友好。

然后luogu题解提供一种减少枚举冗杂的方Fa。我们不是选多个数膜一模吗，如果在膜$P_i$的意义下已经不是$0$了,枚举其他的就没意义了。于是呢，我们先可以选出一个小点的模数$P_x$，在$[1,P_x]$中先枚举一遍，记录多项式值为0的是哪些。最后再枚举$[1,m]$，由于先前的限制，就会减少许多无用选择

然后多项式求值有个叫秦九韶算法的$O(N)$方法,不了解的可以看一看

https://www.cnblogs.com/Rye-Catcher/p/9260599.html

代码

我选择了两个数来做模数，较小的是23333，较大的是19260817

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#define ll long long 
#define ri register int 
using namespace std;
const int maxn=105;
const int inf=0x7fffffff;
const int p1=19260817,p2=71806291,p3=23333;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c=='-';
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;return ;
}
int n,m;
ll a[maxn],c[maxn];
inline void input(int id){
    a[id]=c[id]=0;int ne=0;char ch;
    while(!isdigit(ch=getchar()))ne=ch=='-';
    a[id]=c[id]=ch-48;
    while(isdigit(ch=getchar())){
    	a[id]=((a[id]<<3)%p1+(a[id]<<1)+ch-48)%p1;
    	c[id]=((c[id]<<3)%p3+(c[id]<<1)+ch-48)%p3;
    }
    a[id]=ne?-a[id]:a[id];
    c[id]=ne?-c[id]:c[id];return ;
}
int ans[1000005],tot=0;
bool ok[1000005];
inline bool pre_calc(ll u){
    ll x=0;
    for(ri i=n;i>=0;i--){
        x=(x*u+c[i])%p3;
    }
    return x==0?1:0;
}
inline bool calc(ll u){
    ll x=0;
    for(ri i=n;i>=0;i--){
        x=(x*u+a[i])%p1;
    }
    return x==0?1:0;
}
int main(){
    read(n),read(m);
    for(ri i=0;i<=n;i++){
    	input(i);
    }
    memset(ok,0,sizeof(ok));
    for(ri i=1;i<=p3;i++){
    	if(pre_calc(1ll*i))ok[i]=1;
    }
    for(ri i=1;i<=m;i++)
       if(ok[i%p3]&&calc(1ll*i)){
           ans[++tot]=i;
    }
    printf("%d\n",tot);
    for(ri i=1;i<=tot;i++)printf("%d\n",ans[i]);
    return 0;
}