首页 > 代码库 > 【NOIP2014D2T3】解方程
【NOIP2014D2T3】解方程
神题一道，做了整整两天（其实是一个思路错了然后搞了两天QAQ）
原题：
已知多项式方程：a0+a1*x+a2*x^2+a3^x3+……+an^xn=0
求这个方程在[1, m]内的整数解（n 和 m 均为正整数）。
0<n≤100，|ai|≤10^10000，an≠0，m≤1000000。
这题很神，首先部分分很足，高精度50，万进制或fft应该能拿70，然后正解的思路很奇怪（至少以我现在的水平看来是的）
思路就是如果一个数是0，呢么不管它膜什么数，结果都是0，我们就可以用这个性质来优化算方程的过程
呢么要枚举1-m，然后算，然而这样会T，就需要优化枚举的过程
如果一个数x%k=0，呢么(x+k)%k也是0，枚举的时候就只需要枚举到膜的数就可以代表后面的数
流程大概是酱紫的：
选择5-6个大质数（下面说的都是用5个质数的情况），在输入的时候直接输入数据就膜这五个大质数，然后分别存五个输入数据，表示这五个质数对应的输入数据
枚举内五个质数，然后枚举1-当前的质数，把枚举的东西丢进去算，如果等于零，这个答案就是合法的，否则不合法
如果这五质数搞出来的结果有一个不合法，枚举的东西就不合法
然而上面是这么说的↑，有一点需要注意，枚举的时候不能只用一个数组来+|（或&，都是位运算）来搞，需要先搞五个标记数组，分别对应丢进去算的数分别膜内五个大质数是否合法，在输出的时候再统一验证（即有一个不合法就不合法）
（就是这个问题↑卡了我整两天QAQ）
最后枚举1-m，然后枚举五个大质数，把i膜枚举的质数，然后看对应的标记数组里边是否合法，如果全合法，就进队（要输出个数）
这题脑洞好大……（也许是我太弱了）
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 int n,m; int a[1100][10]; 8 bool can[1100000][6]; 9 int mo[6]={0,11261,19997,22877,21893,14843};10 int dui[1100000],tou=0;11 bool check(int x,int y){12 int z=0;13 for(int i=n;i>=1;i--)14 z=((z+a[i][y])*x)%mo[y];15 return ((z+a[0][y])%mo[y]) ? true : false;//因为memset的问题，所以这里#define false true16 }17 int main(){//freopen("ddd.in","r",stdin);18 memset(can,0,sizeof(can));19 memset(a,0,sizeof(a));20 cin>>n>>m;21 for(int i=0;i<=n;i++){22 int mark=1; char ch=getchar();23 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mark=-1; ch=getchar();}24 while(ch>=‘0‘&&ch<=‘9‘){25 for(int j=1;j<=5;j++)26 a[i][j]=((a[i][j]<<3)+(a[i][j]<<1)+ch-‘0‘)%mo[j];//边读边膜，而且要膜在check的时候膜的内个数27 ch=getchar();28 }29 for(int j=1;j<=5;j++)30 a[i][j]*=mark;31 }32 for(int j=1;j<=5;j++)33 for(int i=1;i<=mo[j]&&i<=m;i++)//如果这个数膜膜的数合法，呢么它加上它膜的内个数也是合法的34 can[i][j]=can[i][j] | check(i,j);35 int i=1;36 for(;i<=m;i++){37 bool _can=false;38 for(int j=1;j<=5;j++){39 int temp=i%mo[j];40 _can=_can | can[temp][j];41 }42 if(!_can) dui[++tou]=i;43 }44 cout<<tou<<endl;45 for(int i=1;i<=tou;i++)46 printf("%d\n",dui[i]);47 return 0;48 }
【NOIP2014D2T3】解方程
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。