解方程


因为a比较大,使用高精度去计算必然会TLE。

于是我们可以利用hash的思想,相当于对等式,两边同时取模。

这里我使用了孪生素数来双hash,增加可靠性。

计算多项式直接秦九韶就行(初中知识应该都会)


AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p1=1e9+7,p2=1e9+3;
int n,m,a[110],b[110];
char str[10010]; vector<int> res;
inline int check(int x){
	int s1=0,s2=0;
	for(int i=n;i>=0;i--)	s1=(s1*x+a[i])%p1,s2=(s2*x+b[i])%p2;
	return (!s1)&&(!s2);
}
signed main(){
	cin>>n>>m;
	for(int i=0,k,flag,len;i<=n;i++){
		scanf("%s",str+1); k=flag=1; len=strlen(str+1);
		if(str[1]=='-')	flag=-1,k++;
		for(int j=k;j<=len;j++)	a[i]=(a[i]*10+str[j]-'0')%p1;
		for(int j=k;j<=len;j++)	b[i]=(b[i]*10+str[j]-'0')%p2;
		a[i]*=flag; b[i]*=flag;
	}
	for(int i=1;i<=m;i++)	if(check(i))	res.push_back(i);
	cout<<res.size()<<'\n';
	for(int i=0;i<res.size();i++)	printf("%d\n",res[i]);
	return 0;
}
全部评论

相关推荐

07-10 11:08
门头沟学院 Java
Sairus:我注册都注册不了提醒我手机号二次啥的,果然对于人才推得就是快,像我投完了就没回音的
投递京东等公司9个岗位
点赞 评论 收藏
分享
绝迹的星:前端和后端写两份简历, 如果想干全栈就直接写求职意向为全栈工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务