whix

分类

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

/ 注册

全部文章（共139篇）

欧拉降幂

公式： 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

解佩尔方程

1.若已知方程x^2-dy ^2=1的最小特解（最小正整数解）x1,y1，那么有迭代公式： xn=xn-1x1+dyn-1y1 yn=xn-1y1+yn-1x1 求出所有的解(xk,yk),可以用矩阵表示如下： |xk|=|x1 dy1| ^(k-1） |x1| |yk| |y1 x1| |y1| ...

2019-08-31

0 661

跳蚤 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

中国剩余定理

若m1,m2,m3,m4,m5,…,mr是两两互素的正整数，则同余方程组 x=a1(mod m1) x=a2(mod m2) x=a3(mod m3) … x=ar(mod mr) 有模 M=m1m2m3…mr的唯一解，即为中国剩余定理。大概思想就是把解用几个数的和的形式来表示，然后利用拓展欧几里...

2019-08-29

0 485

矩阵快速幂专题

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