脚本宝典收集整理的这篇文章主要介绍了君君算法课堂-数论基础，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
对于两个整数 (a , b(aneq 0)) ，若 (exists kin Z) 使 (ak=b) 则称 (a) 整除 (b) ，记做 (a|b)
P1226 【模板】快速幂||取余运算
快速幂用于快速计算 (x^y % mod)
计算的思路是：将十进制的 (y) 看作二进制，再通过二进制下的一些运算统计答案
以下已默认为二进制下的情况
过程：
对于求 (x^y)，将 (y) 表示为二进制，如：(105_{(10)} = 1101001_{(2)})
所以 (x^y = x^{105} = x^{2^6+2^5+2^3+2^0}=x^{2^6}x^{2^5}x^{2^3}x^{2^0})
用变量 (ans) 统计答案
| x | ans |
|---|---|
| (x) | (x^{2^0}) |
| (x^2) | (x^{2^0}) |
| (x^4) | (x^{2^0}) |
| (x^8) | (x^{2^3}x^{2^0}) |
| (x^{16}) | (x^{2^3}x^{2^0}) |
| (x^{32}) | (x^{2^5}x^{2^3}x^{2^0}) |
| (x^{64}) | (x^{2^6}x^{2^5}x^{2^3}x^{2^0}) |
int ksm(int x, int y, int mod) {
int ans = 1;
for( ; y; y >>= 1, (x *= x) %= mod) if(y & 1) (ans *= x) %= mod;
return ans;
}
注：((a *= b) %= mod)的写法等价于 (a = (a * b) %mod)
时间复杂度：(O(log y))
两个数 (a) , (b) 的最大公约数
对于任意 (x , y) 都 (exists a,b) 满足 (ax+by=gcd(x,y))
用来做题
可以用来证明奇奇怪怪的东西和推式子
信息上对于这东西常见的套路是枚举(gcd)
如：给你T组数据,求 (sum_{i=1}^n sum_{j=1}^m gcd(i,j))
其中有一步是标准的枚举 (gcd)
(displaystyle sum_{i=1}^n sum_{j=1}^m gcd(i,j))
(=displaystyle sum_{i=1}^n sum_{j=1}^m sum_{d|i,j}d[gcd(frac id,frac jd)==1])
(mathcal{Code}:)
int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }
P1082 [NOIP2012 提高组] 同余方程
用于求解关于 (x,y) 的方程 (ax+by = gcd(a, b)) 的整数解
方程 (ax + by = m) 有解的必要条件是 (m mod gcd(a, b) = 0)
证明：
由已知条件易得： (a mod gcd(a, b) = 0,b mod gcd(a, b) = 0)
则有 ((ax + by) mod gcd(a, b) = 0)
即为 (m mod gcd(a, b) = 0)
前置知识：欧几里得算法（辗转相除法）
欧几里得算法用于求解两个数的最大公因数
int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }
若我们已经知道以下的式子
则可以得出
则有
当 (b = 0) 时 (ax = a)
此时 (y) 最好取 (0)，因为在回溯时，(y) 的增长较快，容易数值越界
int Ex_gcd(int a, int b, int &x, int &y) {
if(b == 0) return x = 1, y = 0, a;
int ans = Ex_gcd(b, a % b, x, y);
int tmp = x;
x = y; y = tmp - a / b * y;
return ans;
}
这样能够找到方程 (ax+by=gcd(a, b)) 的一组解
若要求解 (x) 为最小正整数的一组解，可由以下公式推导
则 (x = (x % b + b) % b)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int read() {
int x = 0, f = 1; char ch;
while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
int Ex_gcd(int a, int b, int &x, int &y) {
if(b == 0) return x = 1, y = 0, a;
int ans = Ex_gcd(b, a % b, x, y);
int tmp = x;
x = y; y = tmp - a / b * y;
return ans;
}
int main() {
int a = read(), b = read(), x, y;
Ex_gcd(a, b, x, y);
x = (x % b + b) % b;
printf("%dn", x);
return 0;
}
例题：P1516 青蛙的约会
这个真没什么好说的
(lcm) 这东西在数论推柿子里因没有什么性质而遭到嫌弃
通常把 (lcm) 转化为 (gcd) 来做： (lcm(i,j)=frac {i*j}{gcd(i,j)})
注意，这一条性质只在两个数时才成立，其他情况不一定，比如
(frac {1*2*3*4*5}{gcd(1,2,3,4,5)} = 1*2*3*4*5 neq lcm(1,2,3,4,5))
例题：P1891 疯狂LCM
对于两整数 (a , b) 若 (exists p in prime) 使 (a%p == b % p) 则称 (a) 与 (b) 在模 (p) 意义下同余
用符号表示则为 (a equiv b (mod p))
对称性：$a equiv b (mod p) Rightarrow b equiv a (mod p) $
可乘性：若 (a equiv b (mod p) , c equiv d (mod p)) ，则 (ac equiv bd (mod p))
对于信息比较基本，没有什么应用，主要用在定理的证明和表达中
对于同余式 (a equiv b (mod p)) ,可以转化为 (a x+km=b) 就可以应用 exgcd求了
特殊的，对于同余式 (a equiv 1 (mod p)) 的一个解是 (a) 在模 (p) 意义下的逆元
对于整数(a，p)，(exists a^{-1}) 满足 (a*a^{-1} equiv 1(mod p)) 则称 (a^{-1}) 是 (a) 在模 (p) 意义下的逆元
主要用于除法取模问题
因为除法不对模运算封闭，所以逆元应运而生
求逆元主要用两种方法，一是费马小定理，二是 (EX gcd)，三是线性
只列出线性的代码
(mathcal{Code}:)
inv[1] = 1;
for(int i = 2; i <= n; ++ i) inv[i] = ((p - p/i) * inv[p%i]) % p;
例题：P3811 乘法逆元，P5431 乘法逆元2
复杂度 $Theta(n loglogn) $
所以建议用欧拉筛 (Theta(n))
在此讲一下原理
对于一个数 (a) , 则 (k*a (k in N^*)) 一定不会在之后的循环中进入素数表，所以给他们打上标记
因为埃氏筛会对一些数重复筛，所以复杂度就不如欧拉筛优
(mathcal{Code}:)
void calc(){
for(int i = 2; i <= n; ++ i) {
if(! vis[i]) prime[++ cnt] = i;
for(int j = 1; j <= cnt; ++ j) {
if(i * prime[j] <= n) vis[i * prime[j]] = 1;
}
}
}
例题：P3383 线性筛素数
对于一个积性函数 (f)，我们要求 (displaystyle sum_{i=1}^nf(i))
(mathcal{Ans})：
令 (S(n)=displaystylesum_{i=1}^n f(i))，(h=g*f) (h，g为任意积性函数)
则 (displaystylesumlimits_{i=1}^{n}(f*g)(i)) (begin{aligned} &= sumlimits_{i=1}^{n} sum limits _{d|i} g(d)f(frac{i}{d}) \ &= sum limits _{d=1}^{n} g(d)sumlimits _{i=1}^{lfloor frac{n}{d}rfloor } f(i) \ &= sum limits _{d=1}^{n} g(d) S(lfloor frac{n}{d} rfloor) end{aligned})
又 (displaystyle g(1)S(n)=sum_{d=1}^ng(d)S(lfloorfrac ndrfloor)-sum_{d=2}^ng(d)S(lfloorfrac ndrfloor))
则(displaystyle g(1)S(n)=sumlimits_{i=1}^{n}(f*g)(i)-sum_{d=2}^ng(d)S(lfloorfrac ndrfloor))
进行预处理(&)数论分块即可
例题：P4213 杜教筛
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
const int N = 6e6 + 5;
typedef long long LL;
bool vis[N];
int t, cnt, mu[N], phi[N], prime[N], sum1[N];
LL n, sum2[N];
map<int, int> m1;
map<LL, LL> m2;
inline void prim(int x) {
mu[1] = phi[1] = 1;
for(int i = 2; i <= x; i ++) {
if(vis[i] == 0) {
prime[++ cnt] = i;
mu[i] = -1, phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * prime[j] <= x; j ++) {
vis[i * prime[j]] = 1;
if(i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else mu[i * prime[j]] = - mu[i], phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for(int i = 1; i <= x; i ++) sum1[i] = sum1[i-1] + mu[i], sum2[i] = sum2[i-1] + phi[i];
}
int djsmu(int x) {
if(x <= 6e6) return sum1[x];
if(m1[x]) return m1[x];
int ans = 1;
for(int l = 2, r; l <= x; l = r + 1) {
r = x/(x/l);
ans -= (r - l + 1) * djsmu(x/l);
}
return m1[x] = ans;
}
LL djsphi(LL x) {
if(x <= 6e6) return sum2[x];
if(m2[x]) return m2[x];
LL ans = x * (x + 1) / 2;
for(int l = 2, r; l <= x; l = r + 1) {
r = x/(x/l);
ans -= (r - l + 1) * djsphi(x/l);
}
return m2[x] = ans;
}
int main() {
scanf("%d", &t);
prim(6000000);
while(t --> 0) {
scanf("%lld", &n);
printf("%lld %dn", djsphi(n), djsmu(n));
}
return 0;
}
若(m_1,m_2,cdots,m_n)是两两互质的正整数， (M=prod_{i=1}^n{m_i})，(M_i=M/m_i) , (t_i)是线性同余方程(M_it_iequiv 1 (mod m_i))的一个解
对于任意的n个整数(a_1,a_2,cdots,a_n)，则同余方程组： (begin{cases}x≡a_1(mod m_1)\x≡a_2(mod m_2)\ cdots cdots\x≡a_n(mod m_n)\end{cases}) 有整数解
方程组的解为(x=sum_{i=1}^n M_it_i a_i).并且在 (% M) 意义下有唯一解。
因为(M_i=M/m_i) 是除(m_i)之外所有模数的倍数，所以(forall knot=i , M_it_ia_iequiv 0 (mod m_k))
又因为(M_it_ia_iequiv a_i (mod m_i)) 所以 (x=sum_{i=1}^n M_it_i a_i)
(CRT)给出了模数两两互质的线性同余方程组的一个特解。方程组的通解可以表示为 (x+kM (kin Z))。有些题目要求我们求出最小的非负整数解，只需把 (x) 对 (M) 取模，并让x落在 ([1,M)) 内即可。
对于一个多项式 (f(x))，其图像在坐标系内经过 (n) 个点 ((x_i,y_i))
我们考虑对于此多项式的“孙子定理”：
构造 (n) 个多项式 (g_i(n)).对于第 (i) 个多项式，对于(forall knot= i ，g_i(x_k)=0)，而 (g_i(x_i)=1)，即 (g_i(x_i)*y_i=y_i)
则可得 (g_i(x)=frac{(x-x_1)(x-x_2)cdots(x-x_{i-1})(x-x_{i+1})cdots(x-x_n)}{(x_i-x_1)(x_i-x_2)cdots(x_i-x_{i-1})(x_i-x_{i+1})cdots(x_i-x_n)})
所以 (displaystyle f(x)=sum_{i=1}^n g_i(x)*y_i)
(mathcal{Code})：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL N = 2e3 + 5, mod = 998244353;
LL n, k, ans, x[N], y[N];
LL ksm(LL a, LL b) {
int res = 1;
for( ; b ;a = a * a % mod, b >>= 1) {
if(b & 1) res = res * a % mod;
}
return res;
}
LL Lagrange(LL k) {
LL ans = 0;
for(int i = 1;i <= n;i ++) {
LL res = 1;
for(int j = 1;j <= n;j ++) {
if(i == j) continue;
res = (res * ((x[i] + mod - x[j])%mod)) % mod;
}
res = ksm(res, mod - 2);
for(int j = 1;j <= n;j ++) {
if(i == j) continue;
res = (res * ((k + mod - x[j])%mod)) % mod;
}
res = res * y[i] % mod;
ans = (ans + res) % mod;
}
return ans;
}
int main() {
cin >> n >> k;
for(int i = 1;i <= n;i ++) cin >> x[i] >> y[i];
cout << Lagrange(k) << endl;
return 0;
}
例题：P4781 拉格朗日插值
以上是脚本宝典为你收集整理的君君算法课堂-数论基础全部内容，希望文章能够帮你解决君君算法课堂-数论基础所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。