题解：P2312 [NOIP2014 提高组] 解方程

题目大意

在 $1$ 到 $10^6$ 的范围内解一个~~看起来很吓人~~的方程。

分析

对于 $100\%$ 的数据： $0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^6$ 。

相信你一眼就看到了

|a_i|\le 10^{10000}

的离谱范围，但

m

的范围却相对较小。这是，就会~~自然而然的~~想到枚举

x

，来逗答案（四川方言，意为挨个试出答案）。

问题来了，怎么逗？

首先，我问先来表示出题干所给的函数值：

f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2 x^2+ a_1x+a_0

显然，若 $f(x)=0$ ，则 $x$ 为正确答案。

我们来简化一下

f(x)

：

f(x)=a_n x^n+a_{n-1} x^{n-1}+\cdots+a_2 x^2 +a_1x+a_0\\ = (a_nx^{n-1}+a_{n-1}x^{n-2}+\cdots+a_2x+a_1)x+a_0\\ =((a_nx^{n-2}+a_{n-1}x^{n-3}+\cdots+a_2)x+a_1)x+a_0\\ \cdots\\\ =(\cdots((a_nx+a_{n-1})x+\cdots+a_2)x+a_1)x+a_0

若 $f(x)\%mod=0$ ，那 $f(x)$ 就有可能为 $0$ 。
若 $f(x)\%mod=0$ ， $f(x)\%Mod=0$ ，且 $mod\ne Mod$ ，那 $f(x)$ 就很有可能为 $0$ 。

我们就可以用

f(x)

分别对两个数（绝对不能有倍数关系，最好都是质数）取模，看是否为

0

。于是，我们就能通过下面的代码来检验

x

是否为正确答案：

CPP

bool f(int x0,int M,long long *t){//m是模数，t是对应的a数组
	long long res=t[n];
	for(int i=n-1;i>=0;i--) res=(res*x0+t[i])%M;
	return res==0;
}

推到这里，我们就不得不面对

|a_i|\le10^{10000}

的离谱数据。

数值这么大，自然不能用直接读入。我们可以对其进行哈希，利用快读的思想，就能对其进行取模：

CPP

for(int i=0;i<=n;i++){//快读应该都会吧？
	long long x=0,X=0;	bool F=false;	char c=getchar();
	while(c<'0'||'9'<c){if(c=='-') F=true;c=getchar();}
	while('0'<=c&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0',X=(X<<3)+(X<<1)+c-'0';
		x%=mod,X%=Mod;//边乘边取模
		c=getchar();
	}
	a[i]=F?mod-x:x,A[i]=F?Mod-X:X;//这里一定要小心，不要直接拿负数取模！
}

code

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=10007,Mod=1e9+7;
int n,m,cnt,ans[100001];
long long a[102],A[102];
bool vis[mod];

bool f(int x0,int M,long long *t){
	long long res=t[n];
	for(int i=n-1;i>=0;i--) res=(res*x0+t[i])%M;
	return res==0;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++){
		long long x=0,X=0;	bool F=false;	char c=getchar();
		while(c<'0'||'9'<c){if(c=='-') F=true;c=getchar();}
		while('0'<=c&&c<='9'){
			x=(x<<3)+(x<<1)+c-'0',X=(X<<3)+(X<<1)+c-'0';
			x%=mod,X%=Mod;
			c=getchar();
		}
		a[i]=F?mod-x:x,A[i]=F?Mod-X:X;
	}
	for(int i=0;i<mod;i++) if(f(i,mod,a)) vis[i]=true;
	for(int i=1;i<=m;i++) if(vis[i%mod]&&f(i,Mod,A)) ans[++cnt]=i;
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
	return 0;
}

题解：P2312 [NOIP2014 提高组] 解方程

文章操作

题目大意

分析

code

相关推荐

评论

题解：P2312 [NOIP2014 提高组] 解方程