codevs3732==洛谷 解方程P2312 解方程

P2312 解方程

• • 195通过
  • 1.6K提交
• 题目提供者该用户不存在
• 标签数论(数学相关)高精2014NOIp提高组
• 难度提高+/省选-

提交该题 讨论 题解 记录

 

题目描述

已知多项式方程：

a0+a1x+a2x^2+..+anx^n=0

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

输入输出格式

输入格式：

输入文件名为equation .in。

输入共n + 2 行。

第一行包含2 个整数n 、m ，每两个整数之间用一个空格隔开。

接下来的n+1 行每行包含一个整数，依次为a0,a1,a2..an

输出格式：

输出文件名为equation .out 。

第一行输出方程在[1, m ] 内的整数解的个数。

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

输入输出样例

输入样例#1：

2 10 
1
-2
1

输出样例#1：

1
1

输入样例#2：

2 10
2
-3
1

输出样例#2：

2
1
2

输入样例#3：

2 10 
1  
3  
2  
 

输出样例#3：

0

说明

30%:0<n<=2,|ai|<=100,an!=0,m<100

50%:0<n<=100,|ai|<=10^100,an!=0,m<100

70%:0<n<=100,|ai|<=10^10000,an!=0,m<10000

100%:0<n<=100,|ai|<=10^10000,an!=0,m<1000000

 AC代码：

#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long 
#define M 110
#define N 1000100
int n,m,ans;
bool sum[N];
ll a[3][M];
char s[N];
int prime[3]={0,67891,1000000207};
void pre(char *s,int k){
    int len=strlen(s);bool flag=0;
    for(int i=1,start;i<=2;i++){
        start=0;
        if(s[0]=='-'){
            flag=1;
            start=1;
        }
        for(;start<len;start++){
            a[i][k]=(a[i][k]*10LL%prime[i]+s[start]-'0')%prime[i];
        }
        if(flag) a[i][k]=prime[i]-a[i][k];
    }
}
bool judge(int x,int k){
    ll ans=0,b=1;
    for(int i=0;i<=n;i++){
        ans=(ans+1LL*a[k][i]*b)%prime[k];
        b=1LL*b*x%prime[k];
    }
    return ans%prime[k];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(sum,0,sizeof sum);
    for(int i=0;i<=n;i++){
        scanf("%s",s);
        pre(s,i);
    }
    for(int i=1;i<=prime[1];i++){
        if(judge(i,1)) continue;
        for(int j=i;j<=m;j+=prime[1]) if(!judge(j,2)) sum[j]=1;
        //break;//交了5次才发现，QAQ 
    }
    for(int i=1;i<=m;i++) if(sum[i]) ans++;
    printf("%d
",ans);
    for(int i=1;i<=m;i++) if(sum[i]) printf("%d
",i);
    return 0;
}