首页 > 代码库 > 【bzoj3751】[NOIP2014]解方程 数论

【bzoj3751】[NOIP2014]解方程 数论

题目描述

已知多项式方程:

a0+a1*x+a2*x^2+...+an*x^n=0
求这个方程在[1,m]内的整数解(n和m均为正整数)。

输入

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

输出

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

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

样例输入

2 10
2
-3
1

样例输出

2
1
2


题解

真心不难的数论题

首先高精度FFT肯定是不可取的,那么就必须取模。但是只有1个模数极有可能多解,所以多选几个大质数模数,如果左边的式子对所有模数取模都为0,则几乎可以判定为原方程的解。

但是这样时间复杂度为$O(nmt)$,其中t是模数个数,会TLE。

我们设$f(i,j)$表示当左面的一坨的x=i时对j取模得到的数,那么显然$f(i,j)=f(i+j,j)=f(i+2j,j)=...$。

所以我们只需要处理0~j-1的数即可,剩下的直接根据前面的推出来。

这样的时间复杂度为$O(t(np+m))$,其中p为模数大小。

所以p不能太大,但是太小也会影响答案正确性,所以取20000左右的质数最合适。

Tip1:bzoj里的1010000指的是1010000,所以a是高精度数(卡在这里无数次qaq)

Tip2:bzoj这道题加强了(加多了)数据,要数据后发现有40个点,但是时间依然是10s,所以常数卡得很死,不能使用long long,模数最好只有3个等等。

#include <cstdio>#include <cstring>const int tot = 3;int prime[3] = {20029 , 22277 , 23333}; int n , m , a[1000010][3] , ok[100010] , cnt[1000010];char str[1000010];bool judge(int x , int p){	int i , sum = 0;	for(i = n ; ~i ; i -- )		sum = ((sum * x % prime[p] + a[i][p]) % prime[p] + prime[p]) % prime[p];	return !sum;}void read(int c){	scanf("%s" , str);	int i , j , flag = 1 , l = strlen(str);	if(str[0] == ‘-‘)	{		flag = -1;		for(i = 0 ; i < l ; i ++ ) str[i] = str[i + 1];		l -- ;	}	for(i = 0 ; i < tot ; i ++ )	{		int sum = 0;		for(j = 0 ; j < l ; j ++ ) sum = (sum * 10 + str[j] - ‘0‘) % prime[i];		a[c][i] = sum * flag;	}}int main(){	int i , j , num = 0;	scanf("%d%d" , &n , &m);	for(i = 0 ; i <= n ; i ++ ) read(i);	for(i = 0 ; i < tot ; i ++ ) 	{		memset(ok , 0 , sizeof(ok));		for(j = 0 ; j < prime[i] ; j ++ )			if(judge(j , i))				ok[j] = 1;		for(j = 1 ; j <= m ; j ++ ) cnt[j] += ok[j % prime[i]];	}	for(i = 1 ; i <= m ; i ++ )		if(cnt[i] == tot)			num ++ ;	printf("%d\n" , num);	for(i = 1 ; i <= m ; i ++ )		if(cnt[i] == tot)			printf("%d\n" , i);	return 0;}

 

 

【bzoj3751】[NOIP2014]解方程 数论