vijos1910解方程

时间：2023-03-08 18:31:46

描述

已知多项式方程：

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

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

格式

输入格式

输入共 n+2 行。

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

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

输出格式

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

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

样例1

样例输入1[复制] 

2 10

1

-2

1

样例输出1[复制] 

1

1

样例2

样例输入2[复制] 

2 10

2

-3

1

样例输出2[复制] 

2

1

2

样例3

样例输入3[复制] 

2 10

1

3

2

样例输出3[复制] 

0

限制

对于 30%的数据，0 < n ≤ 2， |ai||ai| ≤ 100，anan ≠ 0， m ≤ 100；

对于 50%的数据，0 < n ≤ 100， |ai||ai| ≤ 1010010100 ，anan ≠ 0，m ≤ 100；

对于 70%的数据，0 < n ≤ 100， |ai||ai| ≤ 10100001010000 ，anan ≠ 0，m ≤ 10000；

对于 100%的数据，0 < n ≤ 100， |ai||ai| ≤ 10100001010000 ，anan ≠ 0，m ≤ 1000000。

来源

NOIP2014 提高组 Day2

初看本题，知道要取模一个素数但是有两个地方没考虑

1一个素数不够用，可能要出错，用5个素数就差不多了，这五个素数可以比较小10^4级就可以了

2根据题意如果f（x）=0，那么f（x+p）=0，后面的就不用算了

AC代码

 #include<cstdio>

 #include<iostream>

 #define M 1000002

 #define N 102

 using namespace std;

 int n,m;

 int ans[M];

 int a[N][];

 int t[][];

 int c[][];

 int p[]={,,,,};

 int cal(int y)

 {

     int tmp=;

     for(int i=;i<=n;i++)

     tmp=(tmp+a[i][y]*t[i][y])%p[y];

     if(tmp<)//减法取余要注意可能减到负数

         tmp+=p[y];

     return tmp;

 }

 bool check(int mm)

 {

     for(int i=;i<;i++)

     if(c[mm%p[i]][i]!=)

     return false;

     return true;

 }

 int main()

 {

     cin>>n>>m;

     for(int i=;i<=n;i++)//读大系数

     {

         char ai[];

         scanf("%s",ai);

         for(int k=;k<;k++)

         {

             int factor=;

             int j=;

             if(ai[]=='-')j++;

             for(;;j++)

             {

                 if(ai[j]<=''&&ai[j]>='')

                 factor=(factor*+ai[j]-'')%p[k];

                 else break;

             }

             if(ai[]=='-')

             factor*=-;

             a[i][k]=factor;

         }

     }

     for(int i=;i<;i++)

     for(int j=;j<=p[i];j++)

     {

         t[][i]=;//第一个系数为a0*x^0

         for(int k=;k<=n;k++)t[k][i]=(t[k-][i]*j)%p[i];

         c[j][i]=cal(i);

     }

     for(int i=;i<=m;i++)

     if(check(i))

     ans[++ans[]]=i;

     cout<<ans[]<<endl;

     for(int i=;i<=ans[];i++)

     printf("%d\n",ans[i]);

     return ;

 }

相关文章