NOIP2014解方程

2014年11月22日6,1682

描述

已知多项式方程:

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

样例输入

样例输出

限制

对于 30%的数据,0 < n ≤ 2, |ai| ≤ 100,an ≠ 0, m ≤ 100;

对于 50%的数据,0 < n ≤ 100, |ai|10100an ≠ 0,m ≤ 100;

对于 70%的数据,0 < n ≤ 100, |ai|1010000an ≠ 0,m ≤ 10000;

对于 100%的数据,0 < n ≤ 100, |ai|1010000an ≠ 0,m ≤ 1000000。

题解

本来是不想再看NOIP的题的,毕竟自己考场太逗了TAT 不堪回首

但是bzoj出了这题我不得不来填坑

首先此题30%暴力模拟

50%似乎高精度啥的

70%做法就是对整个方程取模几个值,如果取模后等于0就认为方程等于0,直接枚举方程的解判断即可

由于使用了取模所以避开了高精度

然后发现事实上在 mod p 意义下将 x 与 x+p 带入方程左侧得到答案是相同的,那么只要预处理一下1到p-1带入方程左侧在 mod p 意义下的结果,枚举方程的解就能在 m*pri 的复杂度解决问题,pri是选取的素数个数,随便选五六个就差不多了

 

  • 何宗开2015年7月27日 下午3:16 回复

    我是何宗开,我是ZN!!!!我爱欣欣欣欣爱我!!!!!!

    #1  
  • 杨健2016年9月20日 下午8:55 回复

    黄学长素数选的不好,只能过七个点,9973,9931,9941,9949,9967 这一组数可以ac

    #2