NOIP2014提高组——解方程(equation)

3．解方程

(equation.cpp/c/pas)

【问题描述】

已知多项式方程：

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

 

【输入】

输入文件名为equation.in。

输入共n+2行。

第一行包含2个整数n、m，每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数，依次为a0,a1,a2,……,an。

 

【输出】

输出文件名为equation.out。

第一行输出方程在[1, m]内的整数解的个数。

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

 

【输入输出样例1】

equation.in	equation.out
2 10 1 -2 1	1 1

 

【输入输出样例2】

equation.in	equation.out
2 10 2 -3 1	2 1 2

 

【输入输出样例3】

equation.in	equation.out
2 10 1 3 2	0

 

【数据说明】

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

对于50%的数据，0<n≤100，|ai|≤10¹⁰⁰，an≠0，m≤100；

对于70%的数据，0<n≤100，|ai|≤10¹⁰⁰⁰⁰，an≠0，m≤10000；

对于100%的数据，0<n≤100，|ai|≤10¹⁰⁰⁰⁰，an≠0，m≤1000000。

【解题思路】

这里先说明一下：用普通的方法来算一个n次多项式，需要用2n-1次乘法与n次加法。

这里介绍一个比较快的多项式计算方法：秦九韶算法，可以做到n次乘法和加法。

其实也并不是什么高级的玩意儿，就是：

则实现该算法的代码是：

int calc(int *a,int n,int x)
{
	int sum = 0;
	for(int i=n;i>=0;i--) sum = sum * x + a[i];
	return sum;
}

有了上面简便且快速的计算多项式的算法，可以很容易想到：

若有该方程的某个根x，则：

随便选一个素数（不要太大，容易爆int，也不要太小，容易出大问题），枚举所有的x，若f(x)的值模p等于0，就直接计入答案。

如果对上面的方法不放心，选多几个素数即可。

上述方法的时间复杂度是O(nmk)，其中k是素数的个数。理论上70分。

其实我们没有必要把所有可能的数都算一遍，我们知道：

若有整数p，设之前选的素数为M，则有：

其中，g(x)是关于M的多项式。

所以：

若，则

所以对于每个素数Mi，我们只需要枚举0~Mi-1，若多项式f(x)模Mi不等于0，则用筛法将x,x+Mi,x+2Mi,……全部标记。

对于每个素数都这样做，最后统计出来即可。

时间复杂度。

【程序】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
using namespace std;
#define M 4
int MOD[M]={10007,10917,30071,23333};

bool bo[1000010];
int a[110][M];
char s[10010];
int n,m;

void read()
{
	int sign;

	scanf("%d%d",&n,&m);

	for(int i=0;i<=n;i++)
	{
		scanf("%s",s);
		int len = strlen(s);
		sign = 1;

		for(int j=0;j<len;j++)
		{
			if(s[j] == '-') sign = -1;//若是复数，先做标记 
			else
				for(int k=0;k<M;k++)
					a[i][k] = (a[i][k] * 10 + s[j] - '0') % MOD[k];
		}

		if(sign == -1)
			for(int k=0;k<M;k++) a[i][k] = MOD[k] - a[i][k];//负数取模的性质 
	}
}


bool check(int x,int k)//判断多项式的值是否为0 
{
	long long sum;

	sum = 0;
	for(int i=n;i>=0;i--)
		sum = (sum * (0LL+x) + a[i][k]) % (0LL+MOD[k]);

	return !sum;
}

int main()
{
	read();//读入 

	for(int k=0;k<M;k++) 
	{
		for(int i=1;i<MOD[k];i++)//枚举 
		if(!check(i,k))
		{
			for(int j=0;j + i<=m;j += MOD[k])
				bo[j + i] = true;//用筛法做标记 
		}
	}

	int ans = 0;

	for(int i=1;i<=m;i++) if(!bo[i]) ans++;//统计区间[1,m]的方程整数解的个数 
	printf("%d\n",ans);
	for(int i=1;i<=m;i++) if(!bo[i]) printf("%d\n",i);//输出答案 
	return 0;
}