【NOIP2014提高组】解方程
题目背景
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
1
-2
1
输出
1
1
样例数据 2
输入
2 10
2
-3
1
输出
2
1
2
样例数据 3
输入
2 10
1
3
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%的数据就已经提示了我们。
首先令:
由于当时
所以当时,可能有
为了保证正确性,我们多取几个质数分别进行验证。
又由于:
所以对于每个质数,我们只用验证的数就行了。
代码:
#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;
}
上一篇: 【NOIP2014提高组】石头剪子布
下一篇: 开关灯——计蒜客T1079