1. 首页
  2. 代码宅, 数学问题

【NOIP2014提高组 解方程】

题目背景

NOIP2014 提高组 Day2 试题。

题目描述

已知多项式方程:

a0+a1x+a2x2+…+anxn=0

求这个方程在[1,m]内的整数解(n 和 m 均为正整数)。

输入格式

输入共 n+2 行。
第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数,依次为 a0,a1,a2, … ,an 。

输出格式

第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。

样例数据 1

输入

2 10
1
-2
1

输出

1
1

样例数据 2

输入

2 10
2
-3
1

输出

2
1
2

样例数据 3

输入

2 10
1
3
2

输出

0

备注

【数据范围】
对于 30% 的数据,0<n≤2,|ai|≤100,an≠0,m≤100;
对于 50% 的数据,0<n≤100,|ai|≤10100,an≠0,m≤100;
对于 70% 的数据,0<n≤100,|ai|≤1010000,an≠0,m≤10000;
对于 100% 的数据,0<n≤100,|ai|≤1010000,an≠0,m≤1000000;

看到数据范围傻眼直接暴力30分,据说加个高精度能拿50分,然而看到正解才真是涨姿势了。之前一直不知道对于高次(最高次项>5,此类方程无求解公式)方程有一个非常奇葩的规律。设P是任意一个质数,那么若f(x)%p=0 那么这个x很可能是f(x)=0的解,这道题直接输出就70分了。但是还存在不是解的情况,这时候要多选几个素数来进行测试,若在某个素数中有冲突,那么这就不是解。至于素数的个数,5以内吧,我取的3。大小视题目而定,这道题10000左右足矣。要想过100%的数据,我们发现m太大了,同时若f(x)%p!=0那么f(x+k*p)%p!=0(k∈Z) 所以只用枚举1~p-1,预处理出1~p-1每个x的结果即可,然后再从1~m枚举x的时候对于每个x都mod p,求出来的结果是一样的。

下面是代码:

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

1 条评论

gravatar

*

  1. 沙发

    #-49楼
    Opera 31.0.1889.99Windows 7
    回复
    stdKonjac真是太蠢辣QAQ