转载于博客：

就是把O(n^2)的写法简化到O(n)罢了。

但是这个算法还是对于多项式也是很友好的。

 

1 #include
      
        2 #define N 1001 3 using namespace std; 4 int n,x,a[N],mod; 5 int main() 6 { 7   int ans; 8   scanf("%d%d%d",&n,&x,&mod);//n表示函数f(x)中x的最高次项,mod表示取模数; 9   for(int i=0;i<=n;i++)10     scanf("%d",&a[i]);//a[i]表示每一次项的系数;11   ans=a[n];12   for(int i=n-1;i>=0;i--)13     {14       ans=(ans*x+a[i])%mod;//秦九韶算法主体，数学式为f(x)=(...((a[n]*x+a[n-1])*x+a[n-2])*x+...a[1])*x+a[0];15     }16   printf("%d",ans);17   return 0;18 }