首页 > 代码库 > 【bzoj3751】[NOIP2014]解方程 数论
【bzoj3751】[NOIP2014]解方程 数论
题目描述
已知多项式方程：
a0+a1*x+a2*x^2+...+an*x^n=0
求这个方程在[1,m]内的整数解（n和m均为正整数）。
输入
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,...,an。
输出
第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。
样例输入
2 10
2
-3
1
样例输出
2
1
2
题解
真心不难的数论题
首先高精度FFT肯定是不可取的，那么就必须取模。但是只有1个模数极有可能多解，所以多选几个大质数模数，如果左边的式子对所有模数取模都为0，则几乎可以判定为原方程的解。
但是这样时间复杂度为$O(nmt)$，其中t是模数个数，会TLE。
我们设$f(i,j)$表示当左面的一坨的x=i时对j取模得到的数，那么显然$f(i,j)=f(i+j,j)=f(i+2j,j)=...$。
所以我们只需要处理0~j-1的数即可，剩下的直接根据前面的推出来。
这样的时间复杂度为$O(t(np+m))$，其中p为模数大小。
所以p不能太大，但是太小也会影响答案正确性，所以取20000左右的质数最合适。
Tip1：bzoj里的1010000指的是1010000，所以a是高精度数（卡在这里无数次qaq）
Tip2：bzoj这道题加强了（加多了）数据，要数据后发现有40个点，但是时间依然是10s，所以常数卡得很死，不能使用long long，模数最好只有3个等等。
#include <cstdio>#include <cstring>const int tot = 3;int prime[3] = {20029 , 22277 , 23333}; int n , m , a[1000010][3] , ok[100010] , cnt[1000010];char str[1000010];bool judge(int x , int p){ int i , sum = 0; for(i = n ; ~i ; i -- ) sum = ((sum * x % prime[p] + a[i][p]) % prime[p] + prime[p]) % prime[p]; return !sum;}void read(int c){ scanf("%s" , str); int i , j , flag = 1 , l = strlen(str); if(str[0] == ‘-‘) { flag = -1; for(i = 0 ; i < l ; i ++ ) str[i] = str[i + 1]; l -- ; } for(i = 0 ; i < tot ; i ++ ) { int sum = 0; for(j = 0 ; j < l ; j ++ ) sum = (sum * 10 + str[j] - ‘0‘) % prime[i]; a[c][i] = sum * flag; }}int main(){ int i , j , num = 0; scanf("%d%d" , &n , &m); for(i = 0 ; i <= n ; i ++ ) read(i); for(i = 0 ; i < tot ; i ++ ) { memset(ok , 0 , sizeof(ok)); for(j = 0 ; j < prime[i] ; j ++ ) if(judge(j , i)) ok[j] = 1; for(j = 1 ; j <= m ; j ++ ) cnt[j] += ok[j % prime[i]]; } for(i = 1 ; i <= m ; i ++ ) if(cnt[i] == tot) num ++ ; printf("%d\n" , num); for(i = 1 ; i <= m ; i ++ ) if(cnt[i] == tot) printf("%d\n" , i); return 0;}
【bzoj3751】[NOIP2014]解方程 数论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。