3732 解方程
CODEVS
题目描述 Description

输入描述 Input Description
输入文件名为equation.in。

输入共n+2行。

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

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

输出描述 Output Description
输出文件名为equation.out。

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

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

题解:
可以用秦九韶加速运算,然后取一定的质数然后看是否对于所有的质数这个X都为0,若是这个很有可能就是答案(确实我们就是把这个值作为答案的)。恩就是这样,我一直在写挂,不知道为什么。。。。重新写了好多次

/*
作者:WZH
题目:p3732 解方程
*/
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const long long MAXN = 1000005,PRI[10] = {11261,19997,22877,21893,14843};

long long N,M,sum;
long long Ai[105][10],Bi[100100][10];
bool ans[100100],key;

queue<long long>q;

inline void init(){
    
    scanf("%lld %lld",&N,&M);
    
    for(int i = 0;i <= N;i++){
        int f = 1;char ch = getchar();
        while(ch < '0' || '9' < ch){if(ch == '-') f = -1;ch = getchar();}
        
        while('0' <= ch&& ch <='9'){
            for(int j = 0;j <= 4;j++){
                Ai[i][j] = Ai[i][j] * 10 + ch - '0'; 
                Ai[i][j] %= PRI[j];
            }
            ch = getchar(); 
        }    
        for(int j = 0;j <= 4;j++){
            Ai[i][j] *= f;
        }
    }    
}

inline void count(){  //if ture Fx != 0;
    for(int p = 0;p <= 4;p++){
        for(int i = 1;i <= min(M,PRI[p]-1);i++){
            Bi[i][p] = Ai[N][p];
            for(int j = N - 1;j >= 0;j--){
                Bi[i][p] = (Bi[i][p] * i + Ai[j][p]) % PRI[p];
            }
        }
    }
}
int main(){
    init();
    count();
    for(long long i = 1;i <= M;i++){
    key = false;
        for(int j = 0;j <= 4;j++)
            if(Bi[i % PRI[j]][j])
                key = true;
    if(key == false) sum++,q.push(i);
    }
    
    printf("%lld\n",sum);
    
    while(!q.empty()){
        printf("%lld\n",q.front());
        q.pop();
    }
    
    return 0;
} 
Last modification:October 1st, 2018 at 08:08 am
If you think my article is useful to you, please feel free to appreciate