vijos P1915 解方程 加强版

背景

B酱为NOIP 2014出了一道有趣的题目, 可是在NOIP现场, B酱发现数据规模给错了, 他很伤心, 哭得很可怜.....

为了安慰可怜的B酱, vijos刻意挂出来了真实的题目!

描述

已知多项式方程:

$$a_0+a_1x+a_2x^2+...+a_nx^n=0$$

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

输入格式

输入共 n+2 行。

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

接下来的 n+1 行每行包含一个整数,依次为$a_0,a_1,a_2,...a_n$。

输出格式

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

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

限制

对于20%的数据,$0<n\leq 100$,$|a_i|<=10^{100}$,$a_n \neq 0$,$m\leq 100$;
对于40%的数据,$0<n\leq 100$,$|a_i|<=10^{10000}$,$a_n \neq 0$,$m\leq 10000$;
对于70%的数据,$0<n\leq 100$,$|a_i|<=10^{10000}$,$a_n \neq 0$,$m\leq 1000000=10^6$;
对于100%的数据,$0<n\leq 100$,$|a_i|<=10^{10000}$,$a_n \neq 0$,$m\leq 100000000=10^8$。

[实际上来说就算m <= 10^10也是可以做的, 不过我把时间限制设定为0.5秒,感觉也差不多了。THU某人: O(m)的算法过不去了, 呜呜呜....]

  刚把$noip$的欠账:解方程给补上,又发现了vijos上还有一道加强版。这道题主要就是把$m$的范围加强到了$10^8$,卡掉了$O(m)$的算法。题解戳这里

  不过这道题我把解方程$O(m)$的算法稍微优化了一下,然后就这么过去了……

  原题$O(m)$的算法主要就是自己设一个模数$p$,先把区间$[0,p)$中的解给算出来,然后方程在$x$处的取值就是方程在$x \bmod p$处的取值,于是可以在$O(pn)$的处理后,用$O(m)$的复杂度得到方程在$[1,m]$中的取值。然而这样其实是有非常多的冗余状态的,因为真正对我们有用的位置只是值为$0$的位置。于是我们可以只处理这些位置,分别存到数组中,最后判断一下某个值是否在每个模数下都出现即可。加了这一点优化后即可获得$AC$。

  还有我的这份代码在BZOJ上A不了,需要换一组模数……果然我还是血统不行……

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 110
#define maxn 10010
#define maxm 1000010
#define zushu 4 using namespace std;
typedef long long llg; int p[zushu]={7757,11959,15121,20011},nn[N];
int n,m,l[N],mod,st[N],d[zushu][maxm],ld[zushu];
int ans[maxm],la,ci[maxm],nw[zushu];
char s[N][maxn];
bool fu[maxn<<1]; int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
} int suan(int x){
int ans=0,now=1;
for(int i=0;i<=n;i++){
ans+=nn[i]*now%mod,ans%=mod;
now*=x,now%=mod;
}
return ans;
} void work(){
for(int i=1;i<zushu;i++) nw[i]=1;
for(nw[0]=1;nw[0]<=ld[0];nw[0]++){
bool ww=1;
if(d[0][nw[0]]>m) break;
for(int i=1;i<zushu;i++){
while(d[i][nw[i]]<d[0][nw[0]]) nw[i]++;
if(d[i][nw[i]]!=d[0][nw[0]]) ww=0;
if(nw[i]>ld[i]) return;
}
if(ww) ans[++la]=d[0][nw[0]];
}
} int main(){
File("a");
n=getint(); m=getint();
for(int i=0;i<=n;i++){
scanf("%s",s[i]+1),l[i]=strlen(s[i]+1);
st[i]=(s[i][1]=='-'?2:1); fu[i]=(s[i][1]=='-');
}
for(int i=0;i<zushu;i++){
mod=p[i];
for(int j=0;j<=n;j++){
nn[j]=0;
for(int k=st[j];k<=l[j];k++) nn[j]=nn[j]*10+s[j][k]-'0',nn[j]%=mod;
if(fu[j]) nn[j]=-nn[j];
}
for(int j=0;j<mod;j++) if(!suan(j)) d[i][++ld[i]]=j;
for(int j=1;j<=ld[i];j++)
if(d[i][j]+mod<=m) d[i][++ld[i]]=d[i][j]+mod;
else break;
}
work();
printf("%d\n",la);
for(int i=1;i<=la;i++) printf("%d\n",ans[i]);
return 0;
}

  后天就是$noip$了,我现在还感觉有各种板子没有复习……感觉药丸……

  还有我在想我要不要也开一篇游记什么的……等我复习完了模板再说吧……也许我复习不完了。

上一篇:Run same command on all SQL Server databases without cursors


下一篇:[转] Neutron FWaaS