NOIP2014 D2T3 解方程 BZOJ3751 UOJ20 数论 秦九韶算法 玄学

大家都很强， 可与之共勉 。

话说这是一道简单爆了的难题。

【NOIP2014】解方程

已知多项式方程：

a0+a1x+a2x2+...+anxn=0

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

输入格式

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

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

输出格式

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

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

样例一

input

 
2 10
1
-2
1

output

 
1
1

样例二

input

 
2 10
2
-3
1

output

 
2
1
2

样例三

input

 
2 10
1
3
2

output

 
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 。

时间限制： 1s

内存限制： 128MB

先补充一个知识——秦九韶算法

目的是简化多项式运算

一般地，一元n次多项式的求值需要经过2n-1次乘法和n次加法，而秦九韶算法只需要n次乘法和n次加法。在人工计算时，一次大大简化了运算过程。

把一个n次多项式

改写成如下形式：

求多项式的值时，首先计算最内层括号内一次多项式的值，即

然后由内向外逐层计算一次多项式的值，即

这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。

结论：对于一个n次多项式，至多做n次乘法和n次加法。^[2]  这样，对于一个多项式 已知它的各项系数 ai 就可以这么求值

inline int F ( int* a, int x )  {
    int rt = 0 ;
    for ( int i = n ; ~ i ; -- i ) rt = 1LL * rt * x + a [i] ;
    return rt ; 
}   

如此一来就不用预处理x的次幂是多少，在这一题里会异常方便。

接下来我们来说这道题

显然，若f(x)=0，则f(x)≡f(x0)≡0(mod p)，其中x≡x0(0<=x0 < p)。那么如果f(x0)≡0(mod p)，那么基本可以确定f(x)=0。当然如果不用p取模的话输入早就爆掉了。。那么如果p比较大的话，比如>m，那么取一个质数，基本上出错概率就很小了。
然后我们对系数取模计算的时候取模，若一个数是解，那么它在所有的质数里面的结果（取了模）都应该是0。

详见代码：
UOJ AC 了 BZOJ A不掉mmp
拿UOJ代码交又是OLE又是WA

UOJ AC

开始质数取大了T掉了两个点

# include <bits/stdc++.h>

//const int P1 = 999983, P2 = 882017, P3 = 692009 ;
const int P1 = 11261, P2 = 14843, P3 = 19997 ;

const int N = 105 ;

int n, m ;
int cnt, Ans [1000005] ;
int a1 [N], a2 [N], a3 [N], ans1 [P1], ans2 [P2], ans3 [P3] ;

inline void ReadOpt ( int k )  {
    static char ss [10005] ;
    bool Nagative ( false ) ;
    scanf ( "%s", ss ) ;
    register char* pt = ss ;
    if ( *ss == '-' )  {
        Nagative = true ;
        pt = ss + 1 ;
    }
    while ( *pt )  {
        a1 [k] = ( 10 * a1 [k] + *pt - 48 ) % P1 ;
        a2 [k] = ( 10 * a2 [k] + *pt - 48 ) % P2 ;
        a3 [k] = ( 10 * a3 [k] + *pt - 48 ) % P3 ;
        ++ pt ;
    }
    if ( Nagative )  {
        a1 [k] = ( P1 - a1 [k] ) ;
        a2 [k] = ( P2 - a2 [k] ) ;
        a3 [k] = ( P3 - a3 [k] ) ;
    }
}

inline int Cal ( int* Opt, int x, int P )  {
    int rt = 0 ;
    for ( int i = n ; ~ i ; -- i ) rt = ( 1LL * rt * x + Opt [i] ) % P ;
    return rt ; 
}

int main ( )  {
    scanf ( "%d%d", & n, & m ) ;
    for ( int i = 0 ; i <= n ; ++ i )   ReadOpt ( i ) ;
    for ( int i = 0 ; i < P1 ; ++ i )   ans1 [i] = Cal ( a1, i, P1 ) ;
    for ( int i = 0 ; i < P2 ; ++ i )   ans2 [i] = Cal ( a2, i, P2 ) ;
    for ( int i = 0 ; i < P3 ; ++ i )   ans3 [i] = Cal ( a3, i, P3 ) ;
    for ( register int i = 1 ; i <= m ; ++ i )  {
        if ( ans1 [i % P1] || ans2 [i % P2] || ans3 [i % P3] )  continue ;
        Ans [++ cnt] = i ;
    }
    printf ( "%d\n", cnt ) ;
    for ( int i = 1 ; i <= cnt ; ++ i )
        printf ( "%d\n", Ans [i] ) ;
    return 0 ;
}

BZOJ AC

# include <bits/stdc++.h>

const int P1 = 11261, P2 = 14843, P3 = 19997, P4 = 21893, P5 = 22877 ;

const int N = 105 ;

int n, m ;
int cnt, Ans [1000005] ;
int a1 [N], a2 [N], a3 [N], a4 [N], a5 [N], ans1 [P1], ans2 [P2], ans3 [P3], ans4 [P4], ans5 [P5] ;

inline void ReadOpt ( int k )  {
    static char ss [10005] ;
    bool Nagative ( false ) ;
    scanf ( "%s", ss ) ;
    register char* pt = ss ;
    if ( *ss == '-' )  {
        Nagative = true ;
        pt = ss + 1 ;
    }
    while ( *pt )  {
        a1 [k] = ( 10 * a1 [k] + *pt - 48 ) % P1 ;
        a2 [k] = ( 10 * a2 [k] + *pt - 48 ) % P2 ;
        a3 [k] = ( 10 * a3 [k] + *pt - 48 ) % P3 ;
        a4 [k] = ( 10 * a4 [k] + *pt - 48 ) % P4 ;
        a5 [k] = ( 10 * a5 [k] + *pt - 48 ) % P5 ;
        ++ pt ;
    }
    if ( Nagative )  {
        a1 [k] = ( P1 - a1 [k] ) ;
        a2 [k] = ( P2 - a2 [k] ) ;
        a3 [k] = ( P3 - a3 [k] ) ;
        a4 [k] = ( P4 - a4 [k] ) ;
        a5 [k] = ( P5 - a5 [k] ) ;
    }
}

inline int Cal ( int* Opt, int x, int P )  {
    int rt = 0 ;
    for ( int i = n ; ~ i ; -- i ) rt = ( 1LL * rt * x + Opt [i] ) % P ;
    return rt ; 
}

int main ( )  {
    scanf ( "%d%d", & n, & m ) ;
    for ( int i = 0 ; i <= n ; ++ i )   ReadOpt ( i ) ;
    for ( int i = 0 ; i < P1 ; ++ i )   ans1 [i] = Cal ( a1, i, P1 ) ;
    for ( int i = 0 ; i < P2 ; ++ i )   ans2 [i] = Cal ( a2, i, P2 ) ;
    for ( int i = 0 ; i < P3 ; ++ i )   ans3 [i] = Cal ( a3, i, P3 ) ;
    for ( int i = 0 ; i < P4 ; ++ i )   ans4 [i] = Cal ( a4, i, P4 ) ;
    for ( int i = 0 ; i < P5 ; ++ i )   ans5 [i] = Cal ( a5, i, P5 ) ;
    for ( register int i = 1 ; i <= m ; ++ i )  {
        if ( ans1 [i % P1] || ans2 [i % P2] || ans3 [i % P3] || ans4 [i % P4] || ans5 [i % P5] )    continue ;
        Ans [++ cnt] = i ;
    }
    printf ( "%d\n", cnt ) ;
    for ( int i = 1 ; i <= cnt ; ++ i )
        printf ( "%d\n", Ans [i] ) ;
    return 0 ;
}