NOIP2014解方程
描述
已知多项式方程：
a0+a1x+a2x2+...+anxn=0
求这个方程在[1, m]内的整数解（n 和 m 均为正整数）。
格式
输入格式
输入共 n+2 行。
第一行包含 2 个整数 n、m，每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数，依次为a0,a1,a2,...,an。
输出格式
第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。
样例1
样例输入
样例输出
限制
对于 30%的数据，0 < n ≤ 2， |ai| ≤ 100，an ≠ 0， m ≤ 100；
对于 50%的数据，0 < n ≤ 100， |ai| ≤ 10100 ，an ≠ 0，m ≤ 100；
对于 70%的数据，0 < n ≤ 100， |ai| ≤ 1010000 ，an ≠ 0，m ≤ 10000；
对于 100%的数据，0 < n ≤ 100， |ai| ≤ 1010000 ，an ≠ 0，m ≤ 1000000。
题解
本来是不想再看NOIP的题的，毕竟自己考场太逗了TAT 不堪回首
但是bzoj出了这题我不得不来填坑
首先此题30%暴力模拟
50%似乎高精度啥的
70%做法就是对整个方程取模几个值，如果取模后等于0就认为方程等于0，直接枚举方程的解判断即可
由于使用了取模所以避开了高精度
然后发现事实上在 mod p 意义下将 x 与 x+p 带入方程左侧得到答案是相同的，那么只要预处理一下1到p-1带入方程左侧在 mod p 意义下的结果，枚举方程的解就能在 m*pri 的复杂度解决问题，pri是选取的素数个数，随便选五六个就差不多了
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int mod[5]={11261,19997,22877,21893,14843}; int n,m; int ans[1000005]; int a[5][105],pre[5][105],res[5][30005]; char ch[10005]; inline int cal(int t,int x) { int sum=0; for(int i=0;i<=n;i++) sum=(sum+a[t][i]*pre[t][i])%mod[t]; if(sum<0)sum+=mod[t]; return sum; } inline bool jud(int x) { for(int t=0;t<5;t++) if(res[t][x%mod[t]]!=0)return 0; return 1; } int main() { n=read();m=read(); for(int i=0;i<=n;i++) { scanf("%s",ch+1); int l=strlen(ch+1); bool flag=0; for(int t=0;t<5;t++) if(ch[1]!='-')a[t][i]=ch[1]-'0'; else a[t][i]=0,flag=1; for(int t=0;t<5;t++) { for(int k=2;k<=l;k++) a[t][i]=(a[t][i]*10+ch[k]-'0')%mod[t]; if(flag)a[t][i]=-a[t][i]; } } for(int t=0;t<5;t++) for(int x=1;x<mod[t];x++) { pre[t][0]=1; for(int i=1;i<=n;i++)pre[t][i]=(pre[t][i-1]*x)%mod[t]; res[t][x]=cal(t,x); } for(int i=1;i<=m;i++) if(jud(i))ans[++ans[0]]=i; printf("%d\n",ans[0]); for(int i=1;i<=ans[0];i++) printf("%d\n",ans[i]); return 0; } |
计数器 9325762
OI 课件=>
OI 课件=>
黄学长素数选的不好，只能过七个点，9973,9931,9941,9949,9967 这一组数可以ac
我是何宗开，我是ZN！！！！我爱欣欣欣欣爱我！！！！！！