首页 > 其他分享 >【学习笔记】(14) 初等数论（一）

【学习笔记】(14) 初等数论（一）

时间：2023-06-04 15:44:54浏览次数：52  
标签：ch return 14 数论 large int mod 初等 gcd

1.【最大公约数（GCD）和最小公倍数（LCM）】

【基本性质、定理】

  • \(\large gcd(a,b)=gcd(b,a−b) (a>b)\)

  • \(\large gcd(a,b)=gcd(b,a\) \(\large mod\) \(b)\)

  • \(\large gcd(a,b)\) \(\large lcm(a,b)=ab\)

【推导结论】

  • \(\large k|gcd(a,b)⟺k|a\) 且 \(k|b\)

  • \(\large gcd(k,ab)=1⟺gcd(k,a)=1\) 且 \(gcd(k,b)=1\)

  • $ \large (a+b)∣ab⟹gcd(a,b)≠1$

  • 在 斐波那契数列中求相邻两项的 \(\large gcd\) 时，辗转相减次数等于辗转相除次数。

  • \(\large gcd(F_n,F_m)=F_{gcd(n,m)}\ \ ,\ \ F_n=F_{n-1}+F_{n-2}\)

证明

  1. \(\large gcd(F_n,F_{n-1})=1\)
    证明：\(\large gcd(F_n,f_{n-1})=gcd(F_n-F_{n-1},F_{n-1})=gcd(F_{n-2},F_{n-1})=...=gcd(F_0,f_1)=1\)
  2. \(\large F_{n+m}=F_{n−1}F_m+F_nF_{m+1}\)
    对于 \(\large m=1\) 显然成立。
    手推一下发现 \(\large m=2\) 也成立
    用数学归纳法，若 \(\large m=k-1\) 和 \(\large m=k\) 成立，那么 \(\large m=k+1\) 也成立：

\[\large F_{n+k+1}=F_{n+k}+F_{n+k-1} \]

\[\large = F_{n-1} F_k + F_n F_{k+1} + F_{n-1} F_{k-1} + F_n F_{k} \]

\[\large =F_{n-1}(F_k + F_{k-1})+F_n(F_{k+1}+F_k) \]

\[\large =F_{n-1}F_{k+1}+F_nF_{k+2} \]

  1. \(\large gcd(F_{n+m},F_n)=gcd(F_n,F_m)\)
    \(\large gcd(F_{n+m},F_n)=gcd(F_{n-1}F_m+F_nF_{m+1},F_n)=gcd(F_{n-1}F_m,F_n)=gcd(F_m,F_n)\)
  2. \(\large gcd(F_n,F_m)=F_{gcd(n,m)}\)
    结论3可以写作 \(\large gcd(F_n,F_m)=gcd(F_{n-m},F_m)\)，然后用辗转相减法归纳一下就好了。

2.费马小定理

  • \(\large a^{p-1}≡1 \ \ (mod\ \ p)\)
    引理：当 \(p\) 是质数时，其因子只有 \(1\) 和 \(p\) 两个。因此，若两个数相乘是 \(p\) 的倍数，其中必然至少有一个是 \(p\) 的倍数。
    当 \(a\) 不是 \(p\) 的倍数时，不存在 \(x≠y\) 且 \(1≤x,y<p\) 使得 \(xa≡ya(mod\ \ p)\)。因为据引理，\(x−y\) 是 \(p\) 的倍数，与 \(1≤x,y<p\) 的限制矛盾。

进一步地，考虑 \(1∼p−1\) 所有数，它们乘以 \(a\) 之后在模 \(p\) 意义下的值互不相同，显然同上可以证明两两互不相同，说明仍得 \(1∼p−1\) 所有数。

因此，\(\large \prod\limits_{i=1}^{p-1}i≡\prod\limits_{i=1}^{p-1} ai (mod\ \ p)\) 。又因为$ \large \prod\limits_{i=1}^{p-1}i$ 显然不是 \(p\) 的倍数，所以两边消去

\[\large a^{p−1}≡1(mod\ \ p) \]

根据推导过程，它适用于 \(p\) 是质数且 \(a\) 不是 \(p\) 的倍数的情形。

3.【裴蜀（Bézout）定理】

  • 设 \(\large a,b\) 是不全为零的整数，则存在整数 \(\large x,y\) , 使得 \(\large ax+by=gcd(a,b)\)

  • \(\large gcd(a,b)|d⟺∃x,y∈\mathbb{Z},ax+by=d\)

证明可以使用扩展欧几里得算法来证明

扩展欧几里得算法

扩展欧几里得算法简称扩欧或 exgcd。它是求解最大公约数的欧几里得算法的扩展，用于求解形如 \(\large ax+by=c\) 的 二元线性不定方程。

1.1 解的存在性

先考虑一些较弱的结论。容易发现，无论 \(x,y\) 的取值，左式一定是 \(d=gcd(a,b)\) 的倍数。因此，当 \(d∤c\) 时，方程显然无解。这使得我们可以为方程两侧同时除以 \(d\)。

同时，我们注意到为 \(a\) 和 \(b\) 同时除以 \(d\) 之后，\(a,b\) 互质。这说明我们将问题简化为求解 \(a,b\) 互质时的情形。可见优先判断解的存在性的重要性。

根据直观感受，对于 \(a⊥b\)，\(ax+by\) 似乎能组合成任意一个整数，因为 \(a,b\) 没有共同质因子。显然，只需证明 \(ax\ \ mod\ \ b\) 可以取到 \(0∼b−1\) 当中的任何一个数。

证明很容易，因为 \(a⊥b\)提供了很强的性质。实际上这是将费马小定理的证明中 \(p\) 为质数的条件去掉了，换成了 \(a⊥p\)，本质并没有差别。

证明：考虑 \(ax\) 和 \(ay\) 满足 \(0≤x,y<b\) 且 \(x≠y\)，则 \(ax≢ay(mod\ \ b)\)。若存在，则 \(a(x−y)≡0(mod\ \ b)\)。因为 \(a⊥b\)，所以 \(x−y≡0(mod\ \ b)\)（\(a\) 能够约去的原因是它不提供任何 \(b\) 含有的质因子，也就是对使得 \(a(x−y)≡0(mod\ \ b)\) 成立没有任何贡献），这与 \(0≤x,y<b\) 的限制矛盾。得证。

因为 \(ax+by\) 在 \(a⊥b\) 时取遍所有整数，所以若 \(d∣c\)，方程就一定有解。

综上，我们得到了判断二元线性不定方程 \(ax+by=c\)

存在解的 充要条件：\(gcd(a,b)∣c\)。它被称为 裴蜀定理 或 贝祖定理。

显然裴蜀定理可以推广到 \(n\) 元的情况。 P4549 【模板】裴蜀定理

1.2 算法介绍

欲求解 \(ax+by=c\)，设 \(d=gcd(a,b)\)，我们只需求解 \(ax+by=d\)，并将解乘以 \(cd\) 。根据裴蜀定理，方程的解必然在。

注意到等式右端等于 \(x,y\) 前系数的最大公约数。回顾欧几里得算法（即辗转相除法），我们用到了关键结论 \(gcd(a,b)=gcd(b,a\ \ mod\ \ b)\)，将问题缩至更小的规模上。利用这一思想，我们尝试将求解的方程也缩至更小的规模上。

exgcd 的核心思想与巧妙之处在于 递归构造。假设我们已经得到了 \(bx′+(amodb)y′=d\) 的一组解，则

\[\large ax+by=bx′+(a\ \ mod\ \ b)y′ \]

\[\large \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =bx′+(a−b×⌊\dfrac{a}{b}⌋)y′ \]

\[\large \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =ay′+b(x′−⌊\dfrac{a}{b}⌋y′) \]

对比等式两端，有 \(\large x=y′，y=x′−⌊\dfrac{a}{b}⌋y′\)，递归计算即可。

递归边界即当 \(b=0\) 时，根据辗转相除法，a=d。此时 \(x=1，y=0\) 即为一组解。

上述过程即扩展欧几里得算法，时间复杂度与辗转相除相同。代码如下。

void exgcd(int a, int b, int &x, int &y){
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}

【推导结论】

4.逆元

若 \(ax≡1(mod \ \ p)\)，我们则称 x 为 a 在模 \(p\) 下的逆元，记作 \(x = inv(a)\)。

那逆元用来干什么呢？为了解决模意义下的除法问题，我们引入了逆元。inv(a) 其实可以看做模 \(p\) 意义下的 \(\dfrac{1}{a}\)，那么在模 \(p\) 意义下，\(\dfrac{a}{b}\) 就可以变形为 \(a \times inv(a)\ \ (mod \ \ p)\)。

求逆元常规有以下三种方法：

4.1 费马小定理求逆元

根据费马小定理 \(\large a^{p-1}≡1\ \ (mod \ \ p), gcd(a,p)=1\)。
那么 \(\large a^{-1}≡a^{p-2} \ \ (mod \ \ p)\),据此可快速幂求出一个数在模质数意义下的乘法逆元。

4.2 扩展欧几里得求逆元

\(\large ax≡1 \ \ (mod \ \ p)\) 可以看成 \(\large ax + by = 1\)，这样我们就可以使用扩展欧几里得的方法来解决啦。

从这个方法中我们可以发现， a 存在逆元的冲要条件是 \(a⊥p\)。

P1082 [NOIP2012 提高组] 同余方程

4.3 线性求逆元

  • 如果我们要求 \(n,p\) 求 \(1\sim n\) 中所有整数在模 \(p\) 意义下的乘法逆元。
    那么我们可以使用线性递推法。
    假设 \(1\sim i-1\)的逆元已求得，那么，设 $p=iq+r $，即 $q = ⌊\dfrac{p}{i}⌋, r = p \ \ mod\ \ i $。

\[\large iq+r ≡ 0\ \ (mod \ \ p)\ \ \ \ \ \\ \ \ \ \\ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \\ \ \ \ \\ \ \ \ \ \ \ \ \ \ \\ \ \ \\ \]

\[\large iq≡-r \ \ (mod \ \ p)\ \ \ \ \ \\ \ \ \ \ \ \\ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \]

\[\large i ≡ \dfrac{-r}{q} \ \ (mod \ \ p)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \]

\[\large i ≡ -r\cdot inv(q) \ \ (mod \ \ p)\ \ \\ \ \ \ \]

\[\large inv(i) ≡ -inv(r)\cdot q \ \ (mod \ \ p) \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \]

\[\large inv(i)≡(p - ⌊\dfrac{p}{i}⌋)\cdot inv(p \ \ mod \ \ i) \ \ \ \ \]

  • 如果我们要求任意 n 个数 \(a_i （1\le a_i < p）\)的逆元，设 \(s\) 是 \(a\) 的前缀积，那么可以先用费马求出 \(\large s_n^{-1}\)，然后通过 \(\large s_i^{-1} = s_{i+1}^{-1} \times a_{i+1}\)，则 \(\large a_i^{-1} = s_{i-1} \times s_i^{-1}\)。

P3811 【模板】乘法逆元

5.欧拉函数

5.1 定义与性质

欧拉函数定义为在 \([1,n]\) 中与 \(n\) 互质的整数的个数，记作 \(φ(n)\) 。

int phi(int n){
	int res = n;
	for(int i = 2; i * i <= n; ++i){
		if(n % i == 0) res = res / i * (i - 1);
		while(n % i == 0) n /= i;
	}
	return n > 1 ? res / n * (n - 1) : res;
}

线性筛欧拉函数

根据性质6

for(int i = 2; i <= 1e6; ++i){
	if(!v[i]) p[++tot] = i, phi[i] = i - 1, v[i] = i;
	for(int j = 1; j <= tot && i * p[j] <= 1e6; ++j){
		if(p[j] > v[i]) break;
		v[i * p[j]] = p[j];
		phi[i * p[j]] = phi[i] * (i % p[j] ? p[j] - 1 : p[j]);
	}
}

5.2 欧拉定理



SP5971 LCMSUM - LCM Sum

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 51;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int T, n, tot;
int ans[N], phi[N], p[N], v[N];
void solve(){
	phi[1] = 1;
	for(int i = 2; i <= 1e6; ++i){
		if(!v[i]) p[++tot] = i, phi[i] = i - 1, v[i] = i;
		for(int j = 1; j <= tot && i * p[j] <= 1e6; ++j){
			if(p[j] > v[i]) break;
			v[i * p[j]] = p[j];
			phi[i * p[j]] = phi[i] * (i % p[j] ? p[j] - 1 : p[j]);
		}
	}
	for(int i = 1; i <= 1e6; ++i)
		for(int j = 1; i * j <= 1e6; ++j)
			ans[i * j] += j * phi[j] / 2;
	for(int i = 1; i <= 1e6; ++i) ans[i] = i * ans[i] + i;
}
signed main(){
	T = read();
	solve();
	while(T--){
		n = read();
		printf("%lld\n", ans[n]);
	}
	return 0;
}

P4139 上帝与集合的正确用法

用欧拉定理缩指，发现一直递归下去 \(φ(p)\) 会变成 1，而任何数 \(mod\ \ 1\) 都为 \(0\), 递归结束。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7 + 51;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int T, p, tot;
int v[N], phi[N], pr[N];
void init(){
	phi[1] = 1;
	for(int i = 2; i <= 1e7; ++i){
		if(!v[i]) v[i] = i, phi[i] = i - 1, pr[++tot] = i;
		for(int j = 1; j <= tot && 1ll * pr[j] * i <= 1e7; ++j){
			if(pr[j] > v[i]) break;
			v[i * pr[j]] = pr[j];
			phi[i * pr[j]] = phi[i] * (i % pr[j] ? pr[j] - 1 : pr[j]);
		}
	}
} 
ll qsm(ll a, ll b, ll mod){
	int res = 1;
	for(; b; b >>= 1, a = (a * a) % mod) if(b & 1) res = (res * a) % mod;
	return res; 
} 
ll solve(int mod){
	if(mod == 1) return 0;
	return qsm(2, solve(phi[mod]) + phi[mod], mod);
}
int main(){
	init();
	T = read();
	while(T--){
		p = read();
		printf("%lld\n", solve(p));
	}
	return 0;
}

P3747 [六省联考 2017] 相逢是问候

和上题类似，使用光速幂。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 5e4 + 51, D = 60; 
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, P, c, cntp;
int p[D];
int a[N][D], minn[N << 2];
ll sum[N << 2], c1[D][1 << 15], c2[D][1 << 15];
int phi(int x){
	int ans = x;
	for(int i = 2; i * i <= x; ++i){
		if(x % i) continue;
		while(x % i == 0) x /= i;
		ans = ans / i * (i - 1);
	}
	if(x > 1) ans = ans / x * (x - 1);
	return ans;
}
int mod(ll n, int p){
	return n >= p ? (n % p + p) : n;
}
void init(){
	for(int i = 0; i <= cntp; ++i){
		c1[i][0] = c2[i][0] = 1;
		for(int j = 1; j < 1 << 15; ++j) c1[i][j] = mod((ll) c1[i][j - 1] * c, p[i]);
		c2[i][1] = mod(c1[i][(1 << 15) - 1] * c, p[i]);
		for(int j = 2; j < 1 << 15; ++j) c2[i][j] = mod((ll) c2[i][j - 1] * c2[i][1], p[i]);
	}
}
int csm(int n, int i){
	return mod((ll) c1[i][n % (1 << 15)] * c2[i][n >> 15], p[i]);
}
int solve(int x, int cnt, int i){
	if(!cnt) return mod(x, p[i]);
	if(i == cntp) return 1;
	return csm(solve(x, cnt - 1, i + 1), i);
}
void PushUp(int u){
	minn[u] = min(minn[ls], minn[rs]);
	sum[u] = (sum[ls] + sum[rs]) % P;
}
void Build(int u, int l, int r){
	if(l == r) return minn[u] = 0, sum[u] = a[l][0], void();
	int mid = (l + r) >> 1;
	Build(ls, l, mid), Build(rs, mid + 1, r);
	PushUp(u);
}
void UpDate(int u, int l, int r, int L, int R){
	if(minn[u] > cntp) return ;
	if(l == r) return ++minn[u], sum[u] = a[l][minn[u]], void();
	int mid = (l + r) >> 1;
	if(L <= mid) UpDate(ls, l, mid, L, R);
	if(R > mid) UpDate(rs, mid + 1, r, L, R);
	PushUp(u);
} 
int Query(int u, int l, int r, int L, int R){
	if(L <= l && r <= R) return sum[u];
	int mid = (l + r) >> 1; ll ans = 0;
	if(L <= mid) ans = (ans + Query(ls, l, mid, L, R)) % P;
	if(R > mid) ans = (ans + Query(rs, mid + 1, r, L, R)) % P;
	return ans;
}
int main(){
	n = read(), m = read(), P = read(), c = read();
	p[cntp = 0] = P;
	while(p[cntp] > 1) ++cntp, p[cntp] = phi(p[cntp - 1]); 
	init();
	for(int i = 1; i <= n; ++i){
		a[i][0] = read();
		for(int j = 1; j <= cntp + 1; ++j) a[i][j] = solve(a[i][0], j, 0) % P;
		a[i][0] %= P;
	}
	Build(1, 1, n);
	while(m--){
		int opt = read(), l = read(), r = read();
		if(opt == 0) UpDate(1, 1, n, l, r);
		else printf("%d\n", Query(1, 1, n, l, r));
	}
	return 0;
}

6.离散对数问题

6.1 大步小步算法

int BSGS(int a, int b, int p){
	int A = 1, B = sqrt(p) + 1; a %= p, b %= p;
	gp_hash_table <int, int> mp;
	mp[b] = 0;
	for(int i = 1; i <= B; ++i) mp[(A = A * a % p) * b % p] = i;
	for(int i = 1, AA = A; i <= B; ++i, AA = AA * A % p)
		if(mp.find(AA) != mp.end()) return i * B - mp[AA];
	return -1;
}

容易发现 BSGS 求得的是 \(\log_ab\) 的最小的非负整数解，因为我们从小到大枚举指数。

6.2 扩展大步小步算法

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

BSGS模板题。

点击查看代码 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long 
using namespace std;
using namespace __gnu_pbds;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}
int p, b, m;
int BSGS(int a, int b, int p){
	int A = 1, B = sqrt(p) + 1; a %= p, b %= p;
	gp_hash_table <int, int> mp;
	mp[b] = 0;
	for(int i = 1; i <= B; ++i) mp[(A = A * a % p) * b % p] = i;
	for(int i = 1, AA = A; i <= B; ++i, AA = AA * A % p)
		if(mp.find(AA) != mp.end()) return i * B - mp[AA];
	return -1;
}
signed main(){
	p = read(), b = read(), m = read();
	int ans = BSGS(b, m, p);
	if(~ans) printf("%d\n", ans);
	else printf("no solution\n");
	return 0;
}

P4195 【模板】扩展 BSGS/exBSGS

exBSGS模板题

点击查看代码 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long 
using namespace std;
using namespace __gnu_pbds;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}
int a, b, p;
int BSGS(int a, int b, int p){
	int A = 1, B = sqrt(p) + 1; a %= p, b %= p;
	gp_hash_table <int, int> mp;
	mp[b] = 0;
	for(int i = 1; i <= B; ++i) mp[(A = A * a % p) * b % p] = i;
	for(int i = 1, AA = A; i <= B; ++i, AA = AA * A % p)
		if(mp.find(AA) != mp.end()) return i * B - mp[AA];
	return -1;
}
void exgcd(int a, int b, int &x, int &y){
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int inv(int x, int p){
	return exgcd(x, p, x, *new int), (x % p + p) % p;
}
int exBSGS(int a, int b, int p){
	int d = __gcd(a, p), cnt = 0;
	a %= p, b %= p;
	while(d > 1){
		if(b == 1) return cnt;
		if(b % d) return -1;
		p /= d, b = b / d * inv(a / d, p) % p;
		d = __gcd(p, a %= p), ++cnt;
	}
	int ans = BSGS(a, b, p);
	return ~ans ? ans + cnt : -1;
}
signed main(){
	while(1){
		a = read(), p = read(), b = read();
		if(!p) break;
		int ans = exBSGS(a, b, p);
		if(~ans) printf("%d\n", ans);
		else printf("No Solution\n");
	}
	return 0;
}

7.线性同余方程组

7.1 中国剩余定理

7.2 扩展中国剩余定理

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

点击查看代码 
#include<bits/stdc++.h>
#define N 15
#define int long long
using namespace std;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,M=1,X;
int a[N],b[N],m[N];
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,y,x);
	y-=(a/b)*x;
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),b[i]=read();
		M*=a[i];
	} 
	for(int i=1;i<=n;i++){
		m[i]=M/a[i];
		int x=0,y=0;
		exgcd(m[i],a[i],x,y);
		X+=b[i]*m[i]*((x%a[i]+a[i])%a[i]);
	}
	printf("%lld\n",X%M);
	return 0;
}

P4777 【模板】扩展中国剩余定理（EXCRT）

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 51;
ll read(){
	ll x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
ll n, a, b, c, d;
void exgcd(ll a, ll b, ll &x, ll &y){
	if(!b) return x = 1, y = 0, void();
	exgcd(b, a % b, y, x), y -= a / b * x;
}
int main(){
	n = read(), a = read(), b = read();
	for(int i = 1; i < n; ++i){
		c = read(), d = read();
		ll e = __gcd(a, c), f = (d - b % c + c) % c, inv;
		c /= e, f /= e;
		exgcd(a / e, c, inv, *new long long), inv = (inv % c + c) %c;
		b += (__int128) f * inv % c * a, a *= c, b %= a;
	}
	printf("%lld\n", b);
	return 0;
}

参考:
https://mzwuzad.blog.luogu.org/noip-2017-xiao-kai-di-ni-huo
https://www.cnblogs.com/alex-wei/p/Number_Theory.html
https://www.cnblogs.com/Xing-Ling/p/11990652.html

标签：ch,return,14,数论,large,int,mod,初等,gcd
From： https://www.cnblogs.com/jiangchen4122/p/17417678.html

相关文章

  • 【LGR-141-Div.2】洛谷 6 月月赛 I （前两题）
    T1：金盏花传送门直接暴力枚举前6位的值即可，记得开longlong#include<bits/stdc++.h>usingnamespacestd;#defineintlonglonginty,z,ans=1e18;signedmain(){ scanf("%lld%lld",&y,&z); for(inti=100000;i<=999999;i++){ intx=i*1000000+y; ans=min......
  • P1425 小鱼的游泳时间
    小鱼的游泳时间题目描述伦敦奥运会要到了，小鱼在拼命练习游泳准备参加游泳比赛，可怜的小鱼并不知道鱼类是不能参加人类的奥运会的。这一天，小鱼给自己的游泳时间做了精确的计时（本题中的计时都按$24$小时制计算），它发现自己从$a$时$b$分一直游泳到当天的$c$时$d$分，请你帮小......
  • P1421 小玉买文具
    小玉买文具题目描述班主任给小玉一个任务，到文具店里买尽量多的签字笔。已知一只签字笔的价格是$1$元$9$角，而班主任给小玉的钱是$a$元$b$角，小玉想知道，她最多能买多少只签字笔呢。输入格式输入只有一行两个整数，分别表示$a$和$b$。输出格式输出一行一个整数，表示小玉......
  • odoo14 使用ir.actions.client 自定义弹窗内容
    ir.actions.client介绍ir.actions.client是odooactions事件的一种，触发一个在客户端实现(即js文件中定义的函数，通过core.action_registry.add(tag,函数名)注册到odoo中)动作tag--action在客户端的标识符，一般是一个专用的字符串，在js文件中注册该动作时指定。params(可......
  • 2014.4.25.12.51_context_2014.4.25_Android种的Context详解
    Android中Context详解----你所不知道的Context一、Context相关类的继承关系2二、什么时候创建Context实例5从上可知一下三点,即：1、它描述的是一个应用程序环境的信息，即上下文。2、该类是一个抽象(abstractclass)类，Android提供了该抽象类的具体实现类(后面我们会讲到是Co......
  • 2014.4.19.12.27_switch_8.28_java switch语句使用注意的四大细节_0.01
    javaswitch语句使用注意的四大细节很多朋友在使用javaswitch语句时，可能没有注意到一些细节，本文将详细介绍使用javaswitch语句四大要点,需要的朋友可以参考下。switch语句的格式如下：（它的功能是选出一段代码执行）switch(整数选择因子){case整数值1:语句;break;case整数值......
  • 三个博弈-巴什博奕、威佐夫博弈、尼姆博弈。acm博弈算法笔记HDU 2149,1850,1527
    博弈论（一）、acm博弈基础算法BashGame,NimGame和WythoffGame（即巴什博奕、尼姆博弈、威佐夫博弈）Bash  Game: 同余理论Nim   Game: 异或理论WythoffGame: 黄金分割（二）、三个博弈。1、巴什博奕。只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，......
  • 5.14 static 应用案例
    demo1publicclassHelloWorld{publicstaticvoidmain(String[]args){print();//静态方法调用静态方法;}publicstaticvoidprint(){System.out.println("www.mldn.cn");}}lastdemopublicclassHelloWorld{publ......
  • Multisim14.0软件安装教程Multisim14.0软件安装包下载
    [名称]：Multisim14.0[大小]：685.23MB[语言]：中/英文 [适用系统]：win7,win8,win10,win11[简介]：Multisim是一款以win系统为基础的电路仿真工具，该软件功能非常强大，具有丰富的仿真分析能力，可以有效帮助用户完成实验工作，是一款非常不错的电路图设计软件。[64位下载地址]：https://pan.baidu.c......
  • AtCoder Beginner Contest 214 G Three Permutations
    洛谷传送门AtCoder传送门比较平凡的一个容斥。考虑把问题转化成，求\(\foralli\in[1,n],r_i\nei\landr_i\nep_i\)的\(r\)方案数。考虑到不弱于错排，所以容斥。设钦定\(i\)个\(r_i\)取了\(i,p_i\)中的一个的方案数为\(f_i\)，其余任意，那么：\[ans=\sum\limi......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99