whix

数论

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

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

容斥定理专题

介绍 Co-prime HDU - 4135 用位运算生成所有可能 #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int N=1e3+5; ll a...

2019-09-04

0 349

欧拉降幂

公式： n^x mod m=n ^(φ(m)+x%φ(m)) 当且仅当x>φ(m)时成立。更具体有关题目 hdu2837 模板题： #include <cstdio>//欧拉降幂 #include <cstring> using namespace std; ...

2019-09-04

0 662

欧拉函数

1.首先明确积性函数对于算术函数f(x)如果如果对于任意两个互质的正整数n,m，有f(nm)=f(n)*f(m),那么称该函数为积性函数。如果对任意两个正整数n,m都满足f(nm)=f(n)*f(m)，那么称为完全积性函数。 2.欧拉函数的概念 φ(n)；表示不大于n,并且和n互质的数的个数（包...

2019-09-02

0 761

跳蚤 POJ - 1091

质因子分解+容斥定理 #include <cstdio> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int N=1e5+5; int...

2019-08-31

0 525

解不定方程

1.二元一次不定方程 ax+by=c 直接用拓展欧几里得算法，加上判断是否有解。c%gcd==0 同时知道通解的表示。 2.n元一次不定方程模板(https://blog.csdn.net/cFarmerReally/article/details/52203470) 题目: poj1091

2019-08-30

0 428

矩阵快速幂专题

poj3233 经典题因为k的值太大，如果直接算，肯定会超时。因此采用二分的方法。 #include <cstdio> #include <cstring> using namespace std; int n,k,m; struct matrix { int ...

2019-08-26

0 459

高次同余方程

详解下面的模板中是，调用函数时是A,B,C A^x=B(mod C) poj3243(模板题) #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> u...

2019-08-26

0 436

线性同余方程

一.一元线性同余方程形如 ax=b(mod m)，a,b,为整数，m为正整数，x为未知数的同余式称为一元线性同余方程。方程可以变形为：ax+my=c （1）而对于方程 ax+by=(a,b) (2)是一定有解的。因此可以把方程（1）转化为方程（2）求解。利用拓展欧几里得算法，解出方程（2）...

2019-08-25

0 551

Reduced ID Numbers POJ - 2769

思路：暴力枚举 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=1e6-1; int SIN[305],maxn; bool v...

2019-08-24

0 441

Prime Distance POJ - 2689

大区间素数查找。因为给出的数据范围太大，无法开到那么大的数组，所以不可以一开始预处理出所有的素数。又因为l和u之间的差值最大1e6,所以也不可能一个一个地去判断。正确的方法时，先预处理出 sqrt(N)范围内的全部素数，那么就可以通过这些素数来判断1~N内的所有数是素数还是合数。对于给定的区...

2019-08-24

0 421