欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP2014提高组】解方程

程序员文章站 2024-03-18 21:46:10
...

题目背景

NOIP2014 提高组 Day2 试题。

题目描述

已知多项式方程:

    a0+a1^x+a2^x2+…+an^xn=0

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

输入格式

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

输出格式

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

样例数据 1

输入

2 10 

-2 
1

输出


1

样例数据 2

输入

2 10 

-3 
1

输出



2

样例数据 3

输入

2 10 


2

输出

0

备注

【数据范围】 
对于 30% 的数据,0<n≤2,|ai|≤100,an≠0,m≤100;
对于 50% 的数据,0<n≤100,|ai|≤10100,an≠0,m≤100; 
对于 70% 的数据,0<n≤100,|ai|≤1010000,an≠0,m≤10000; 
对于 100% 的数据,0<n≤100,|ai|≤1010000,an≠0,m≤1000000;

 

解析:

       刚看到题着实被吓到了。。。

       后来向dalao请教后发现又是一道用非正常思路解的题。。。

       首先对于30%的数据暴力带进去模拟。

       对于50%的数据用高精度。

       对于70%的数据。做法就是对整个方程取模几个值,如果取模后等于0就认为方程等于0,直接枚举方程的解判断即可由于使用了取模所以避开了高精度。

       对于100%的数据。70%的数据就已经提示了我们。

       首先令:

       【NOIP2014提高组】解方程

       由于当【NOIP2014提高组】解方程【NOIP2014提高组】解方程

       所以当【NOIP2014提高组】解方程时,可能有【NOIP2014提高组】解方程

       为了保证正确性,我们多取几个质数分别进行验证。

       又由于:

       【NOIP2014提高组】解方程

       所以对于每个质数,我们只用验证【NOIP2014提高组】解方程的数就行了。

 

代码:

#include <bits/stdc++.h>
using namespace std;

const int p[7]={0,967,971,977,983,991,997};
const int Max=1000010;
int n,m,ans;
int num[105][7],vis[Max],f[1005][7];

inline void get_int(int id)
{
	int f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') f=-1,c=getchar();
	for(;isdigit(c);c=getchar())
	  for(int i=1;i<=6;i++) num[id][i]=((num[id][i]<<3)+(num[id][i]<<1)+c-'0')%p[i];
	if(f==-1) for(int i=1;i<=6;i++) num[id][i]=-num[id][i];
}

inline bool check(int x,int y)
{
	int sum=0;
	for(int i=n;i;i--) sum=(sum+num[i][y])*x%p[y];
	sum=(sum+num[0][y])%p[y]; 
	if(!sum) return 1;
	return 0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) get_int(i);
	for(int i=1;i<=6;i++)
	  for(int j=0;j<p[i];j++)
	    f[j][i]=check(j,i);
	for(int i=1;i<=m;i++)
	{
	  int tag=1;
	  for(int j=1;j<=6;j++) if(!f[i%p[j]][j]) {tag=0;break;}
	  if(tag) ans++,vis[i]=1;
	}
	cout<<ans<<"\n";
	for(int i=1;i<=m;i++) if(vis[i]) cout<<i<<"\n";
	return 0;
}

 

相关标签: NOIP真题