LOJ2503 NOIP2014 解方程


LINK


题目大意就是给你一个方程,让你求[1,m]中的解,其中系数非常大


看到是提高T3还是解方程就以为是神仙数学题

后来研究了一下高精之类的算法发现过不了多少分

后面佬说这题是hash

然后就雾


考虑对于一个式子f(x)=0肯定会满足f(x)%prime=0
所以我们直接多取几个相近的prime,减小冲突几率

然后我们只需要预处理每个系数对于每个prime的模数,然后判断一下就可以了

但是这样会TLE

又可以发现对于任意的f(x)%prime=0,等价于f(x%prime)%prime=0
所以对于每个质数直接枚举比它小的数进行检查就好了

然后就比较和谐了

中间出了一些比较玄学的错误导致交了很多个70分
不过问题不大


 #include<bits/stdc++.h>
using namespace std;
#define N 110
#define M 1000010
int prime[]={,,,,};
int pa[N][],n,m;
char c[M];
bool vis[M],ak[M][];
int check(int x,int id){
int pic=;
for(int i=n;i>=;i--)
pic=(pic*x%prime[id]+pa[i][id])%prime[id];
return pic;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",c);
int len=strlen(c),j=;
if(c[]=='-')j++;
for(;j<len;j++)for(int k=;k<;k++)
pa[i][k]=(pa[i][k]*+c[j]-'')%prime[k];
if(c[]=='-')for(int k=;k<;k++)pa[i][k]*=-;
}
int cnt=;
for(int j=;j<;j++)
for(int i=;i<prime[j];i++)
if(check(i,j)!=)ak[i][j]=;
for(int i=;i<=m;i++){
bool can=;
for(int j=;j<;j++)if(ak[i%prime[j]][j]){can=;break;}
if(can)vis[i]=,cnt++;
}
printf("%d\n",cnt);
for(int i=;i<=m;i++)if(vis[i])printf("%d\n",i);
return ;
}

最新文章

  1. ABP框架 - 工作单元
  2. linux下进程权限分析
  3. iOS之02-第一个OC的类
  4. CSS:CSS定位和浮动
  5. malloc心得
  6. HTML5 随音乐节奏变化的频谱图动画
  7. Java 时间转换问题总结
  8. Chronodex:视觉时间管理,让你的生活更有序
  9. Spring第一个例子的补充
  10. 【★】KMP算法完整教程
  11. [Swift]LeetCode700. 二叉搜索树中的搜索 | Search in a Binary Search Tree
  12. Linux文件误删之后恢复方法
  13. SuperMap空间数据处理与制图操作短视频汇总
  14. PAT A1097 Deduplication on a Linked List (25 分)——链表
  15. BZOJ 4808: 马(二分图最大点独立集)
  16. 【转】Code First 属性详解
  17. shell字符串基本操作
  18. JQ_开发经验
  19. python 普通文件读写
  20. 用Python实现BP神经网络(附代码)

热门文章

  1. Springboot-mongodb MongoRepository接口 save方法 详解
  2. oracle快速创建主键
  3. Maven打可执行包的pom.xml配置
  4. 理解OpenID和OAuth的区别
  5. SPOJ-394-ACODE - Alphacode / dp
  6. 不使用构造方法创建Java对象: objenesis的基本使用方法
  7. yyyy-MM-dd EEE hh:mm:ss(日期转换)
  8. nodejs利用express操作mysql增删改查
  9. C# ASP.NET 验证码
  10. bzoj3495