游客 注册 | 登录
中文 | En

3408 - 解方程

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

已知多项式方程：
�!+�!�+�!�
!+⋯+�!�
!=0
求这个方程在[1, m]内的整数解（n和m均为正整数）

题目输入

输入文件名为equation.in。
输入共n+2行。
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为�!
,�!
,�!
,…,�!

题目输出

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

输入/输出样例

输入格式

2 10
1
-2
1

输出格式

1
1

C++解答

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 110
using namespace std;
typedef long long ll;
const int prime[]={10007,11261,14843,19997,21893};
int n,m,stack[1001001],top;
ll a[M][5],f[21893][5];
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<5;j++)
                a[x][j]=((a[x][j]<<1)+(a[x][j]<<3)+s[i]-'0')%prime[j];
    }
    if(flag)for(j=0;j<5;j++)a[x][j]=prime[j]-a[x][j];
}
int main(){
    int i,j;
    cin>>n>>m;
    for(i=0;i<=n;i++)
        Input(i);
    for(j=0;j<5;j++)
        for(i=0;i<prime[j];i++)
            f[i][j]=F(i,j);
    for(i=1;i<=m;i++){
        for(j=0;j<5;j++)
            if(f[i%prime[j]][j])break;
        if(j==5)stack[++top]=i;
    }
    cout<<top<<endl;
    for(i=1;i<=top;i++)printf("%d\n",stack[i]);
}
请先登陆