【NOIP14 D2T3】解方程

Source and Judge

NOIP2014 提高组 D2T3
Bzoj3751
Luogu2312
Caioj1568

Problem

【Description】
已知多项式方程:
$$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$$
求这个方程在 $[1,m]$ 内的整数解($n$ 和 $m$ 均为正整数)。
【Input】
输入共 $n + 2$ 行。
第一行包含 $2$ 个整数 $n, m$,每两个整数之间用一个空格隔开。
接下来的 $n+1$ 行每行包含一个整数,依次为 $a_0,a_1,a_2\ldots a_n$。
【Output】
第一行输出方程在 $[1,m]$ 内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在 $[1,m]$ 内的一个整数解。
【Limited conditions】
对于 $30\%$ 的数据:$0<n\le 2,|a_i|\le 100,a_n≠0,m<100$。
对于 $50\%$ 的数据:$0<n\le 100,|a_i|\le 10^{100},a_n≠0,m<100$。
对于 $70\%$ 的数据:$0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^4$。
对于 $100\%$ 的数据:$0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^6$。
【Sample input 1】
2 10
1
-2
1
【Sample output 1】
1
1
【Sample input 2】
2 10
2
-3
1
【Sample output 2】
2
1
2
【Sample input 3】
2 10
1
3
2
【Sample output 3】
0
【Sample explanation】

Record

40min

Analysis

请先思考后再展开

一开始想着高精度肯定超时啊
然后膜题解,发现自己忘记了这个套路:自然溢出,或者搞多几个模数
之前也用过:等价表达式
原理还是类似的:如果$f(x)=0$,那么$f(x)\%p=0$,而这个多项式又没有除法

然后用秦九昭就好了
这东西之前看到,结果就觉得:傻逼玩意……
然后现在居然没想到了
感觉这东西和韦达定理是一个道理的……

但是现在的复杂度大概是1亿的,然后还有个long long的常数5,还有两个模数的常数2
有没有很虚的感觉?那怎么办么?随便卡卡常呗
随便搞个小模数10007吧,这里面的数字,如果$f(x)=0$,
那么后面的部分(即$f(10007\times b+x)$)显然就不用枚举了
不知道为什么就快了非常多呀(好像时间复杂度证明跟拉格朗日定理有关?)

Code

请先思考后再展开
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
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
//*******************全局常量*******************
const int MAXN=1100000;
const int MOD[5]={11261,19997,22877,21893,14843};
//*******************全局定义*******************
int a[5][MAXN];
bool v[5][MAXN];
int ans[MAXN],as=0;
//*******************实现*******************
int n;
bool check(int x,int mod,int *f)
{
int sum=0;
for(int i=n;i>=0;i--) sum=(sum*x%mod+f[i])%mod;
return sum==0;
}
//*******************主函数*******************
char s[MAXN];
int main()
{
int m;scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
scanf("%s",s+1);int ln=strlen(s+1);
int fg=1;
for(int j=1;j<=ln;j++)
{
if(s[j]=='-') {fg=-1;continue;}
for(int t=0;t<5;t++) a[t][i]=(a[t][i]*10+s[j]-'0')%MOD[t];
}
for(int t=0;t<5;t++) a[t][i]*=fg;
}
for(int t=0;t<5;t++) for(int i=1;i<MOD[t];i++) v[t][i]=check(i,MOD[t],a[t]);
for(int i=1;i<=m;i++)
if(v[0][i%MOD[0]] and v[1][i%MOD[1]] and v[2][i%MOD[2]]
and v[3][i%MOD[3]] and v[4][i%MOD[4]]) ans[++as]=i;
printf("%d\n",as);
for(int i=1;i<=as;i++) printf("%d\n",ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-05/解方程.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%