CODEVS 3732: [NOIP2014]解方程
Time Limit: 1 Sec Memory Limit: 128 MB
Description
Input
输入共n+2行。
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,……,an。
Output
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
Hint
【数论噩梦系列】%%%数学省队同桌
--------------------------------0-------------------------------
妈呀这题我不会【滑稽再见】。
-------------------------------30-------------------------------
CCF的30%枚举拿拿还是很开心的【括弧笑】。
-------------------------------50-------------------------------
50%高精模拟？
听说某位线段树大师写挂了2333。
----------------------------思考人生----------------------------
怎么搞呢？
脑子想想都觉得100%高精不靠谱（高精加减乘方复杂度怎么看就愉♂悦）。
把范围缩小？
有没有听过这样一句话：由于XXXX的方案数太多，输出时要对100000007取模。
好熟悉的梗！
于是Get了一个新姿势：
-------------------------------70-------------------------------
选取几个较大素数（例如10000-20000之间的）
对于每个x，算出f(x)%pi，如果f(x)=0则f(x)%pi必然=0，多选几个素数，就可以在一定范围大小内判断成功。
但是不够快QAQ
-------------------------二段思考人生--------------------------
70拿拿也蛮好的，就当总分570做！
不对，这是练习，不是比赛现场。
搜题解：【定理：f(x)≡f(x+p)%p 这里f(x)为整系数多项式】
真TM机智！（二项式定理可以眼秒证明）
------------------------------100-------------------------------
对于一个x，f(x)≠0(mod p)，则x+p,x+2p……均不为方程的解。
筛法大法好！
------------------------------150-------------------------------
m<=10^8
https://vijos.org/p/1915/solution @doc @sujiao
100分脑残Code：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define M 110#define R 6#define G getchar()using namespace std;int a[10005],A[M],P[R]={30011,11261,14843,19997,10007,21893},N,H[M][R],L,S=0,V,p,X,sum,x,n,m,W;bool C[1000005];char ch;int main(){ scanf("%d%d\n",&n,&m); for (int i=0;i<=n;i++) { L=0; if ((ch=G)=='-') N=-1; else a[L++]=ch-48,N=1; while ((ch=G)>47)a[L++]=ch-48; scanf("\n"); for (int p=0;p<R;p++) { W=0; for (int w=0;w<L;w++)W=(W*10+a[w])%P[p]; H[i][p]=(P[p]+W*N)%P[p]; } } for (int i=1;i<=m;i++) { V=1; if (C[i]) continue; for (int j=0;j<R;j++) { p=P[j],x=i%p,sum=0,X=1; for (int k=0;k<=n;k++) sum=(sum+X*H[k][j])%p,X=(X*x)%p; if (sum) { for (int k=i;k<=m;k+=P[j])C[k]=1; V=0;break; } } if (V) A[++S]=i; } printf("%d\n",S); for (int i=1;i<=S;i++) printf("%d\n",A[i]); return 0;} |
150分Code：(由于O(n^3+n*sqrt(m))导致常规数据下比O(m)慢)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | #include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define maxn 110#define pri 4using namespace std;typedef long long LL;int a[10010],prime[4]={10007,10009,12007,13001},neg,hehe[110][4],l;int s[110][2],la[2],anss[110],ans;char ch;void gcd(LL a,LL b,LL& d,LL& x,LL &y)//ax+by=d{ if (!b)d=a,x=1,y=0; else gcd(b,a%b,d,y,x),y-=x*(a/b);}LL CRT(LL a1,LL p1,LL a2,LL p2)//%a1=p1 %a2=p2{ LL s=a2-a1,k1,k2,pp=p1*p2,d; gcd(p1,-p2,d,k1,k2); s=(s%pp+pp)%pp; k1=(k1%pp+pp)%pp; //d=1; k1=k1*s%pp; return (k1*p1%pp+a1%pp)%pp;}int main(){ int n,m; scanf("%d%d\n",&n,&m); for (int i=0;i<=n;i++) { l=0; ch=getchar(); if (ch=='-') neg=-1; else {a[l++]=ch-48;neg=1;} ch=getchar(); while (ch<=57&&ch>=48) { a[l++]=ch-48; ch=getchar(); } scanf("\n"); for (int p=0;p<pri;p++) { int ans=0; for (int w=0;w<l;w++) ans=(ans*10+a[w])%prime[p]; hehe[i][p]=(prime[p]+ans*neg)%prime[p]; } } int ans=0; for(int A=0;A<2;A++) { for (int i=1;i<=prime[A];i++)//枚举答案 { int p=prime[A],x=i%p,sum=0,X=1; for (int k=0;k<=n;k++)// sum=(sum+X*hehe[k][A])%p,X=(X*x)%p; if (!sum) {s[++la[A]][A]=i;} } } for(int I=1;I<=la[0];I++) for(int J=1;J<=la[1];J++) { int vic=1,i=CRT(s[I][0],prime[0],s[J][1],prime[1]); if(i>m)continue; for (int j=0;j<pri;j++)//判素数 { int p=prime[j],x=i%p,sum=0,X=1; for (int k=0;k<=n;k++)// sum=(sum+X*hehe[k][j])%p,X=(X*x)%p; if (sum) { vic=0; break; } } if (vic) {anss[++ans]=i;} } if(!ans)puts("0"); else { sort(anss+1,anss+1+ans); printf("%d\n",ans); for (int i=1;i<=ans;i++) printf("%d\n",anss[i]); } return 0;} |
2015年11月05日 21:44
%%%快去做解方程加强版！
https://vijos.org/p/1915