YZBPXX

数论

acm入门练习(1) c#(1) c++，c实用小函数，操作(20) hash/bkdr hash字符串(2) 动态规划—树形dp(1) 动态规划—背包九讲(7) 单调栈(1) 图论—bfs(2) 图论—dfs(6) 图论—最小生成树(1) 图论—最短单源路径(5) 字符串—ac自动机(1) 字符串—扩展KMP/KMP(4) 字符串—马拉车(1) 带权并查集(2) 拓扑排序(2) 数据库学习(6) 数据结构—RMQ(5) 数据结构—字典树(1) 数据结构--红黑二叉树(1) 未归档(2) 矩阵快速幂(1) 算法分析(3) 网络流(1) 集训题(2) 题解(33)

/ 注册

全部文章 / 数论（共8篇）

luogu P3868 猜数字

https://www.luogu.org/problem/P3868 题目描述：给你k个a[i],b[i] 其中(x-a[i])%b[i]=0 求解最小非负解分析：这个题解决了一些中国剩余定理的模糊点，首先等式不难推到变形得x=a[i](mod b[i]) 这里注意几点 ...

中国剩余定理

2019-08-17

0 630

中国剩余定理

问题：给你几组同余方程组让你输出他的解附上学习链接在加些自己的理解：https://blog.csdn.net/niiick/article/details/80229217 首先构造一个x使得满足上述的方程，因为取模等于所以选择累乘而 , ti 是这样，...

2019-08-17

0 517

欧拉函数欧拉定理及欧拉降幂

欧拉函数表示小于等于x的素数有多少个如几个性质： 1、euler(1)=1（唯一和1互质的数就是1本身）。 2、若n是质数p的k次幂，φ(n) = p^k - p^(k-1) = (p - 1)*p^(k - 1)，因为p为质数，所以与n不互质的数只有p的倍数，一共有p^(k...

2019-07-30

0 1119

逆元（分数取模）

及ax=1(modn) 　　求解x（称为a关于模p的乘法逆元）分析有：原式等价于ax-1=yn, 求解x,y; 及exgcd(x,y) 并且gcd(x,y)=1 也就是互质时有解； exgcd求逆元代码： void exgcd(int a,int b,int &...

模版

2019-07-19

0 1668

扩展欧几里德

必存在一对整数(x,y) 使得a*x+b*y=gcd(a,b); gcd（a,b）= gcd(b,a%b) （辗转相除法）又 a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2; 又b*x2+(a%b)*y2=b*x2+(a-[a/b]*b)*...

2019-07-19

0 484

取模的n种情况

一减法　　(a-b)%mod=(a%mod-b%mod+n)%mod; 二大数　　有乘法取模可推出如下代码 string s; cin>>s; int ans=0,len=s.length(); for(int i=0;i...

2019-07-14

0 445

Eratos筛法（筛选素数）

对于n以内的非素数必有k*n1=n(n1<n) 所以可有p1，2p2,3p3把非素数筛选掉实现代码： #include<iostream> #include<string.h> #include<math.h> using namespace...

2019-07-14

0 469

扩展欧几里得

必存在一对整数(x,y) 使得a*x+b*y=gcd(a,b); gcd（a,b）= gcd(b,a%b) （辗转相除法）又 a*x1+b*y1=gcd(a,b)=gcd(b,a%b)=b*x2+(a%b)*y2; 又b*x2+(a%b)*y2=b*x2+(a-[a/b]*b)*y2=a*y...

2019-07-14

0 671