首页 > 代码库 > NOIP201410解方程（C++）
NOIP201410解方程（C++）
| NOIP201410解方程 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
已知多项式方程：
a0+a1*x+a2*x^2+a3*x^3+…+an*x^n=0
求这个方程在[1, m]内的整数解（n 和 m 均为正整数）。
|
|
输入
|
|
输入共 n+2 行。
第一行包含 2 个整数 n、m，每两个整数之间用一个空格隔开。接下来的 n+1 行每行包含一个整数，依次为a0,a1,a2…an。 |
|
输出
|
|
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。 |
|
输入示例
|
|
2 10
2 -3 1 |
|
输出示例
|
|
2
1 2 |
|
其他说明
|
|
对于 100% 的数据，0 < n ≤ 100， ai ≤ 10^10000 ，an ≠ 0，m ≤ 1000000。
|
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 110
using namespace std;
typedef long long ll;
const int prime[]={30011,11261,14843,19997,10007,21893};
int n,m,stack[1001001],top;
int ans[110],tot;
ll a[M][6],f[30011][6];
inline ll F(int x,int j)
{
int i;
ll re=0;
for(i=n;~i;i--)
re=(re*x+a[i][j])%prime[j];
return re;
}
inline void Input(int x)
{
static char s[10100];
int i,j;
bool flag=false;
scanf("%s",s+1);
for(i=1;s[i];i++)
{
if(s[i]==‘-‘)
flag=true;
else
for(j=0;j<6;j++)
a[x][j]=( (a[x][j]<<1) + (a[x][j]<<3) + s[i]-‘0‘ )%prime[j];
}
if(flag)
for(j=0;j<6;j++)
a[x][j]=prime[j]-a[x][j];
}
int main()
{
//freopen("equation.in","r",stdin);
int i,j;
cin>>n>>m;
for(i=0;i<=n;i++)
Input(i);
for(j=0;j<6;j++)
for(i=0;i<prime[j];i++)
f[i][j]=F(i,j);
for(i=0;i<prime[0];i++)
{
if(f[i%prime[0]][0]==0)
stack[++top]=i;
}
for(i=1;i<=top;i++)
{
if(stack[i]+prime[0]>m)
break;
stack[++top]=stack[i]+prime[0];
}
for(i=1;i<=top;i++)
{
if(stack[i]>m)
break;
for(j=1;j<6;j++)
if(f[stack[i]%prime[j]][j])
break;
if(j==6)
ans[++tot]=stack[i];
}
cout<<tot<<endl;
for(i=1;i<=tot;i++)
printf("%d\n",ans[i]);
}
NOIP201410解方程（C++）