本文最后更新于 957 天前,其中的信息可能已经有所发展或是发生改变。
概念
质数又称素数 ,一个大于1 1 1 的自然数,除了1 1 1 和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数 (规定1既不是质数也不是合数)
思想
N < 2 N<2 N < 2 不是质数
从i = 2 i=2 i = 2 开始枚举,直到n \sqrt{n} n ,若i i i 能被N N N 整除,说明不是质数
反之,则为质数
模板
bool is_prime (int n) {
if (n<2 ) return 0 ;
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ) return 0 ;
}
return 1 ;
}
例题 866. 试除法判定质数
原题链接
描述
给定 n 个正整数 ai,判定每个数是否是质数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
共 n 行,其中第 i 行输出第 i 个正整数 ai 是否为质数,是则输出 Yes,否则输出 No。
数据范围
1≤n≤100,
1≤ai≤2^31−1
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
bool is_prime (int n) {
if (n<2 ) return 0 ;
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ) return 0 ;
}
return 1 ;
}
int main () {
int t;
cin >>t;
while (t--){
int x;
cin >>x;
if (is_prime(x)) cout <<"Yes" <<endl ;
else cout <<"No" <<endl ;
}
return 0 ;
}
概念
每个合数都可以写成几个质数 相乘的形式,其中每个质数都是这个合数 的因数
把一个合数用质因数乘积的形式表示出来,叫做分解质因数
如30 = 2 × 3 × 5 30=2\times3\times5 30 = 2 × 3 × 5 ,分解质因数只针对合数 。
思想
算术基本定理 :任何一个大于1 1 1 的自然数N N N ,如果N N N 不为质数
那么N N N 可以唯一分解成有限个质数的乘积N = p 1 a 1 × p 2 a 2 ⋯ × p i a k N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k} N = p 1 a 1 × p 2 a 2 ⋯ × p i a k ,且最多只有一个大于n \sqrt{n} n 的质因子
这里p 1 < p 2 < p 3 … p i p_1<p_2<p_3\dots p_i p 1 < p 2 < p 3 … p i 均为质数,其中指数a k a_k a k 是正整数
模板
map <int ,int > primes;
void get_div (int n) {
primes.clear();
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
while (n%i==0 ){
primes[i]++;
n/=i;
}
}
}
if (n>1 ) primes[n]++;
}
例题 867. 分解质因数
原题链接
描述
给定 n 个正整数 ai,将每个数分解质因数,并按照质因数从小到大的顺序输出每个质因数的底数和指数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
对于每个正整数 ai,按照从小到大的顺序输出其分解质因数后,每个质因数的底数和指数,每个底数和指数占一行。
每个正整数的质因数全部输出完毕后,输出一个空行。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
map <int ,int > primes;
void get_div (int n) {
primes.clear();
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
while (n%i==0 ){
primes[i]++;
n/=i;
}
}
}
if (n>1 ) primes[n]++;
}
int main () {
int n;
cin >>n;
while (n--){
int x;
cin >>x;
get_div(x);
for (auto &p : primes) cout <<p.first<<" " <<p.second<<endl ;
cout <<endl ;
}
return 0 ;
}
思想
对于1 ∼ N 1\sim N 1 ∼ N 中的一个合数n n n
从小到大枚举筛选出的质数p p p ,将1 ∼ N 1\sim N 1 ∼ N 范围内质数p p p 的倍数的合数筛掉
从而保证了n n n 只会被其最小质因子p j p_j p j 筛掉,且一定会在枚举到p j × n p j p_j\times\frac{n}{p_j} p j × p j n 之前筛掉
模板
int cnt;
int primes[N];
bool vis[N];
void get_primes (int n) {
for (int i=2 ;i<=n;i++){
if (!vis[i]) primes[cnt++]=i;
for (int j=0 ;primes[j]<=n/i;j++){
vis[primes[j]*i]=1 ;
if (i%primes[j]==0 ) break ;
}
}
}
例题 868. 筛质数
原题链接
描述
给定一个正整数 n,请你求出 1∼n 中质数的个数。
输入格式
共一行,包含整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中质数的个数。
数据范围
1≤n≤106
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=1e6 +3 ;
int cnt;
int primes[N];
bool vis[N];
void get_primes (int n) {
for (int i=2 ;i<=n;i++){
if (!vis[i]) primes[cnt++]=i;
for (int j=0 ;primes[j]<=n/i;j++){
vis[primes[j]*i]=1 ;
if (i%primes[j]==0 ) break ;
}
}
}
int main () {
int n;
cin >>n;
get_primes(n);
cout <<cnt<<endl ;
return 0 ;
}
概念
约数,又称因数 。整数a a a 除以整数b ( b ≠ 0 ) b(b≠0) b ( b = 0 ) 除得的商正好是整数而没有余数 ,我们就说a a a 能被b b b 整除,或b b b 能整除a a a 。a a a 称为b b b 的倍数 ,b b b 称为a a a 的约数 。
思想
从i = 1 i=1 i = 1 开始枚举到N \sqrt{N} N
i i i 和N i \frac{N}{i} i N 即为N N N 的约数
模板
const int N=1e6 +3 ;
int res[N];
int cnt;
void get_div (int n) {
cnt=0 ;
for (int i=1 ;i<=n/i;i++){
if (n%i==0 ){
res[cnt++]=i;
if (i!=n/i) res[cnt++]=n/i;
}
}
sort(res,res+cnt);
}
例题 869. 试除法求约数
原题链接
描述
给定 n 个正整数 ai,对于每个整数 ai,请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出共 n 行,其中第 i 行输出第 i 个整数 ai 的所有约数。
数据范围
1≤n≤100,
2≤ai≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=1e6 +3 ;
int res[N];
int cnt;
void get_div (int n) {
cnt=0 ;
for (int i=1 ;i<=n/i;i++){
if (n%i==0 ){
res[cnt++]=i;
if (i!=n/i) res[cnt++]=n/i;
}
}
sort(res,res+cnt);
}
int main () {
int n;
cin >>n;
while (n--){
int x;
cin >>x;
get_div(x);
for (int i=0 ;i<cnt;i++) cout <<res[i]<<" " ;
cout <<endl ;
}
return 0 ;
}
思想
算术基本定理 :任何一个大于1 1 1 的自然数N N N ,如果N N N 不为质数
那么N N N 可以唯一分解成有限个质数的乘积N = p 1 a 1 × p 2 a 2 ⋯ × p i a k N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k} N = p 1 a 1 × p 2 a 2 ⋯ × p i a k ,且最多只有一个大于n \sqrt{n} n 的质因子
这里p 1 < p 2 < p 3 … p n p_1<p_2<p_3\dots p_n p 1 < p 2 < p 3 … p n 均为质数,其中指数a i a_i a i 是正整数
设d d d 为N N N 的任意一个约数,d = p 1 b 1 × p 2 b 2 ⋯ × p i b j d=p_1^{b_1}\times p_2^{b_2}\dots\times p_i^{b_j} d = p 1 b 1 × p 2 b 2 ⋯ × p i b j ,其中0 < b j < a k 0<b_j<a_k 0 < b j < a k
由算术基本定理可知对于d d d 中的p i b j p_i^{b_j} p i b j 项,b j b_j b j 取值不同,则d d d 不同( 每个数的因式分解是唯一的 ) (每个数的因式分解是唯一的) ( 每个数的因式分解是唯一的 )
故N N N 的约数个数= = = d d d 的个数= = = b j b_j b j 的选法总数{ p 1 共有 0 ∼ a 1 种选法 p 2 共有 0 ∼ a 2 种选法 p 3 共有 0 ∼ a 3 种选法 p i 共有 0 ∼ a k 种选法
\begin{cases}
p_1共有0\sim a_1种选法\\
p_2共有0\sim a_2种选法\\
p_3共有0\sim a_3种选法\\
p_i共有0\sim a_k种选法\\
\end{cases}
⎩ ⎨ ⎧ p 1 共有 0 ∼ a 1 种选法 p 2 共有 0 ∼ a 2 种选法 p 3 共有 0 ∼ a 3 种选法 p i 共有 0 ∼ a k 种选法
根据乘法原理可知:N N N 的约数个数为( a 1 + 1 ) × ( a 2 + 1 ) × ( a 3 + 1 ) × ⋯ × ( a k + 1 ) (a_1+1)\times(a_2+1)\times(a_3+1)\times\dots\times(a_k+1) ( a 1 + 1 ) × ( a 2 + 1 ) × ( a 3 + 1 ) × ⋯ × ( a k + 1 )
模板例题 870. 约数个数
原题链接
描述
给定 n 个正整数 ai,请你输出这些数的乘积的约数个数,答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
const LL mod=1e9 +7 ;
LL cnt=1 ;
map <int ,int > primes;
void get_div (int n) {
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
while (n%i==0 ){
primes[i]++;
n/=i;
}
}
}
if (n>1 ) primes[n]++;
}
int main () {
int n;
cin >>n;
while (n--){
int x;
cin >>x;
get_div(x);
}
for (auto &p : primes) cnt=cnt*(p.second+1 )%mod;
cout <<cnt<<endl ;
return 0 ;
}
思想
算术基本定理 :任何一个大于1 1 1 的自然数N N N ,如果N N N 不为质数
那么N N N 可以唯一分解成有限个质数的乘积N = p 1 a 1 × p 2 a 2 ⋯ × p i a k N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k} N = p 1 a 1 × p 2 a 2 ⋯ × p i a k ,且最多只有一个大于n \sqrt{n} n 的质因子
这里p 1 < p 2 < p 3 … p i p_1<p_2<p_3\dots p_i p 1 < p 2 < p 3 … p i 均为质数,其中指数a k a_k a k 是正整数
{ p 1 的约数之和 = p 1 0 + p 1 1 + ⋯ + p 1 a 1 p 2 的约数之和 = p 2 0 + p 2 1 + ⋯ + p 2 a 2 p 3 的约数之和 = p 3 0 + p 3 1 + ⋯ + p 3 a 3 … p i 的约数之和 = p i 0 + p i 1 + ⋯ + p i a k
\begin{cases}
p_1的约数之和=p_1^{0}+p_1^{1}+\dots+p_1^{a_1}\\
p_2的约数之和=p_2^{0}+p_2^{1}+\dots+p_2^{a_2}\\
p_3的约数之和=p_3^{0}+p_3^{1}+\dots+p_3^{a_3}\\
~~~~~~~~~~~~~~~~~~~~~\dots\\
p_i的约数之和=p_i^{0}+p_i^{1}+\dots+p_i^{a_k}\\
\end{cases}
⎩ ⎨ ⎧ p 1 的约数之和 = p 1 0 + p 1 1 + ⋯ + p 1 a 1 p 2 的约数之和 = p 2 0 + p 2 1 + ⋯ + p 2 a 2 p 3 的约数之和 = p 3 0 + p 3 1 + ⋯ + p 3 a 3 … p i 的约数之和 = p i 0 + p i 1 + ⋯ + p i a k
根据乘法原理可知:N N N 的约数之和= ( p 1 0 + p 1 1 + ⋯ + p 1 a 1 ) × ( p 2 0 + p 2 1 + ⋯ + p 2 a 2 ) × ⋯ × ( p i 0 + p i 1 + ⋯ + p i a k ) =(p_1^{0}+p_1^{1}+\dots+p_1^{a_1})\times(p_2^{0}+p_2^{1}+\dots+p_2^{a_2})\times\dots\times(p_i^{0}+p_i^{1}+\dots+p_i^{a_k}) = ( p 1 0 + p 1 1 + ⋯ + p 1 a 1 ) × ( p 2 0 + p 2 1 + ⋯ + p 2 a 2 ) × ⋯ × ( p i 0 + p i 1 + ⋯ + p i a k )
模板例题 871. 约数之和
原题链接
描述
给定 n 个正整数 ai,请你输出这些数的乘积的约数之和,答案对 109+7 取模。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个整数 ai。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对 109+7 取模。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
const LL mod=1e9 +7 ;
LL res=1 ;
map <int ,int > primes;
void get_div (int n) {
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
while (n%i==0 ){
primes[i]++;
n/=i;
}
}
}
if (n>1 ) primes[n]++;
}
int main () {
int n;
cin >>n;
while (n--){
int x;
cin >>x;
get_div(x);
}
for (auto &p : primes){
LL t=1 ;
int a=p.first,b=p.second;
while (b--){
t=(t*a+1 )%mod;
}
res=res*t%mod;
}
cout <<res<<endl ;
return 0 ;
}
概念
最大公约数指两个或多个整数共有约(因)数中最大的数
最小公倍数指两个或多个整数的公倍数里最小的数
思想
辗转相除法求最大公约数
例如: 假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法,是这样进行的:
100 / 18 = 5 (余 10)
18 / 10= 1(余8)
10 / 8 = 1(余2)
8 / 2 = 4 (余0)
至此,最大公约数为2
以除数和余数反复做除法运算,当余数为 0 时,取当前算式除数为最大公约数,所以就得出了 100 和 18 的最大公约数2。
求N N N 和M M M 的最小公倍数l c m ( N , M ) lcm(N,M) l c m ( N , M ) ,则先求N N N 和M M M 的最大公约数g c d ( N , M ) gcd(N,M) g c d ( N , M ) ,然后N × M g c d ( N , M ) \frac{N\times M}{gcd(N,M)} g c d ( N , M ) N × M 则为最小公倍数。
模板
int gcd (int a, int b) {
return b ? gcd(b, a % b) : a;
}
int lcm (int a,int b) {
return a/gcd(a,b)*b;
}
概念
1 ∼ N 1∼N 1 ∼ N 中与N N N 互质的数的个数被称为欧拉函数,记为 ϕ ( N ) \phi(N) ϕ ( N ) ,特别的ϕ ( 1 ) = 1 \phi(1)=1 ϕ ( 1 ) = 1
欧拉函数是一个积性函数,若m m m ,n n n 互质,则有ϕ ( m × n ) = ϕ ( m ) × ϕ ( n ) \phi(m\times n)=\phi(m)\times\phi(n) ϕ ( m × n ) = ϕ ( m ) × ϕ ( n )
思想
算术基本定理 :任何一个大于1 1 1 的自然数N N N ,如果N N N 不为质数
那么N N N 可以唯一分解成有限个质数的乘积N = p 1 a 1 × p 2 a 2 ⋯ × p i a k N=p_1^{a_1}\times p_2^{a_2}\dots\times p_i^{a_k} N = p 1 a 1 × p 2 a 2 ⋯ × p i a k ,且最多只有一个大于n \sqrt{n} n 的质因子
这里p 1 < p 2 < p 3 … p i p_1<p_2<p_3\dots p_i p 1 < p 2 < p 3 … p i 均为质数,其中指数a k a_k a k 是正整数
则ϕ ( N ) = ϕ ( p 1 a 1 ) × ϕ ( p 2 a 2 ) × ⋯ × ϕ ( p n a n ) \phi(N)=\phi(p_1^{a_1})\times\phi(p_2^{a_2})\times\dots\times\phi(p_n^{a_n}) ϕ ( N ) = ϕ ( p 1 a 1 ) × ϕ ( p 2 a 2 ) × ⋯ × ϕ ( p n a n )
对于任意一项ϕ ( p i a i ) \phi(p_i^{a_i}) ϕ ( p i a i ) ,与p i a i p_i^{a_i} p i a i 不互质的数有p i , 2 × p i , 3 × p i , … , p i ( a i − 1 ) × p i p_i,2\times p_i,3\times p_i,\dots,p_i^{(a_i-1)}\times p_i p i , 2 × p i , 3 × p i , … , p i ( a i − 1 ) × p i 共p i ( a i − 1 ) p_i^{(a_i-1)} p i ( a i − 1 ) 项
即ϕ ( p i a i ) = p i a i − p i ( a i − 1 ) \phi(p_i^{a_i})=p_i^{a_i}-p_i^{(a_i-1)} ϕ ( p i a i ) = p i a i − p i ( a i − 1 )
ϕ ( N ) = ϕ ( p 1 a 1 ) × ϕ ( p 2 a 2 ) × ⋯ × ϕ ( p n a n ) = ( p 1 a 1 − p 1 ( a 1 − 1 ) ) × ( p 2 a 2 − p 2 ( a 2 − 1 ) ) × ⋯ × ( p n a n − p n ( a n − 1 ) ) = p 1 a 1 × p 2 a 2 × ⋯ × p n a n × ( 1 − 1 p 1 ) × ( 1 − 1 p 2 ) × ⋯ × ( 1 − 1 p n ) = N × ∏ i = 1 n ( 1 − 1 p i )
\begin{aligned}
\phi(N)&=\phi(p_1^{a_1})\times\phi(p_2^{a_2})\times\dots\times\phi(p_n^{a_n})\\
&=(p_1^{a_1}-p_1^{(a_1-1)})\times(p_2^{a_2}-p_2^{(a_2-1)})\times\dots\times(p_n^{a_n}-p_n^{(a_n-1)})\\
&=p_1^{a_1}\times p_2^{a_2}\times\dots\times p_n^{a_n}\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\dots\times(1-\frac{1}{p_n})\\
&=N\times\prod^{n}_{i=1}{(1-\frac{1}{p_i})}
\end{aligned}
ϕ ( N ) = ϕ ( p 1 a 1 ) × ϕ ( p 2 a 2 ) × ⋯ × ϕ ( p n a n ) = ( p 1 a 1 − p 1 ( a 1 − 1 ) ) × ( p 2 a 2 − p 2 ( a 2 − 1 ) ) × ⋯ × ( p n a n − p n ( a n − 1 ) ) = p 1 a 1 × p 2 a 2 × ⋯ × p n a n × ( 1 − p 1 1 ) × ( 1 − p 2 1 ) × ⋯ × ( 1 − p n 1 ) = N × i = 1 ∏ n ( 1 − p i 1 )
模板
typedef long long LL;
LL phi (LL n) {
LL res=n;
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
res=res/i*(i-1 );
while (n%i==0 ) n/=i;
}
}
if (n>1 ) res=res/n*(n-1 );
return res;
}
例题 873. 欧拉函数
原题链接
描述
给定 n 个正整数 ai,请你求出每个数的欧拉函数。
欧拉函数的定义
1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。
若在算数基本定理中,N=pa11pa22…pamm,则:
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个正整数 ai。
输出格式
输出共 n 行,每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
LL phi (LL n) {
LL res=n;
for (int i=2 ;i<=n/i;i++){
if (n%i==0 ){
res=res/i*(i-1 );
while (n%i==0 ) n/=i;
}
}
if (n>1 ) res=res/n*(n-1 );
return res;
}
int main () {
int n;
cin >>n;
while (n--){
int x;
cin >>x;
cout <<phi(x)<<endl ;
}
return 0 ;
}
思想
利用线性筛,在筛选1 ∼ N 1\sim N 1 ∼ N 中的质数时,将1 ∼ N 1\sim N 1 ∼ N 的欧拉函数ϕ ( P i ) \phi(P_i) ϕ ( P i ) 求出
对于质数P i P_i P i ,其ϕ ( P i ) = P × ( 1 − 1 P ) = P − 1 \phi(P_i)=P\times(1-\frac{1}{P})=P-1 ϕ ( P i ) = P × ( 1 − P 1 ) = P − 1
对于合数P i P_i P i ,其ϕ ( P i ) = N × ∏ i = 1 n ( 1 − 1 p i ) \phi(P_i)=N\times\prod^{n}_{i=1}{(1-\frac{1}{p_i})} ϕ ( P i ) = N × ∏ i = 1 n ( 1 − p i 1 )
在线性筛法求质数的模板中利用最小质因子筛掉合数的过程时:
当i % p r i m e s [ j ] = 0 i\%primes[j]=0 i % p r im es [ j ] = 0 时,说明p r i m e s [ j ] primes[j] p r im es [ j ] 是i i i 的一个质因子,且p r i m e s [ j ] primes[j] p r im es [ j ] 是p r i m e s [ j ] × i primes[j]\times i p r im es [ j ] × i 的一个质因子,故ϕ ( i ) \phi(i) ϕ ( i ) 包含( 1 − 1 p r i m e s [ j ] ) (1-\frac{1}{primes[j]}) ( 1 − p r im es [ j ] 1 ) 的情况,即ϕ ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × ϕ ( i ) \phi(primes[j]\times i)=primes[j]\times\phi(i) ϕ ( p r im es [ j ] × i ) = p r im es [ j ] × ϕ ( i )
当i % p r i m e s [ j ] ≠ 0 i\%primes[j]\ne 0 i % p r im es [ j ] = 0 时 ,说明p r i m e s [ j ] primes[j] p r im es [ j ] 是i i i 的最小质因子,且p r i m e s [ j ] primes[j] p r im es [ j ] 不是p r i m e s [ j ] × i primes[j]\times i p r im es [ j ] × i 的一个质因子,故ϕ ( i ) \phi(i) ϕ ( i ) 不包含( 1 − 1 p r i m e s [ j ] ) (1-\frac{1}{primes[j]}) ( 1 − p r im es [ j ] 1 ) 的情况,即ϕ ( p r i m e s [ j ] × i ) = p r i m e s [ j ] × ϕ ( i ) × ( 1 − 1 p r i m e s [ j ] ) = ( p r i m e s [ j ] − 1 ) × ϕ ( i ) \begin{aligned}\phi(primes[j]\times i)&=primes[j]\times\phi(i)\times(1-\frac{1}{primes[j]})\ &=(primes[j]-1)\times\phi(i)\end{aligned} ϕ ( p r im es [ j ] × i ) = p r im es [ j ] × ϕ ( i ) × ( 1 − p r im es [ j ] 1 ) = ( p r im es [ j ] − 1 ) × ϕ ( i )
模板
int primes[N];
bool vis[N];
int phi[N];
int cnt;
void get_phi (int n) {
phi[1 ]=1 ;
for (int i=2 ;i<=n;i++){
if (!vis[i]){
primes[cnt++]=i;
phi[i]=i-1 ;
}
for (int j=0 ;primes[j]<=n/i;j++){
vis[primes[j]*i]=1 ;
if (i%primes[j]==0 ){
phi[primes[j]*i]=primes[j]*phi[i];
break ;
}
else phi[primes[j]*i]=(primes[j]-1 )*phi[i];
}
}
}
例题 874. 筛法求欧拉函数
原题链接
描述
给定一个正整数 n,求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行,包含一个整数 n。
输出格式
共一行,包含一个整数,表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=1e6 +3 ;
typedef long long LL;
int primes[N];
bool vis[N];
int phi[N];
int cnt;
void get_phi (int n) {
phi[1 ]=1 ;
for (int i=2 ;i<=n;i++){
if (!vis[i]){
primes[cnt++]=i;
phi[i]=i-1 ;
}
for (int j=0 ;primes[j]<=n/i;j++){
vis[primes[j]*i]=1 ;
if (i%primes[j]==0 ){
phi[primes[j]*i]=primes[j]*phi[i];
break ;
}
else phi[primes[j]*i]=(primes[j]-1 )*phi[i];
}
}
}
int main () {
int n;
cin >>n;
get_phi(n);
LL res=0 ;
for (int i=1 ;i<=n;i++){
res+=phi[i];
}
cout <<res<<endl ;
return 0 ;
}
概念
快速求出a k m o d p a^k\mod p a k mod p 的结果
思想
预处理出a 2 0 , a 2 1 , a 2 2 … a 2 l o g 2 k a^{2^0},a^{2^1},a^{2^2}\dots a^{2^{log_2^k}} a 2 0 , a 2 1 , a 2 2 … a 2 l o g 2 k 的结果
则使得k = 2 p 1 + 2 p 2 + ⋯ + 2 p i k=2^{p_1}+2^{p_2}+\dots+2^{p_i} k = 2 p 1 + 2 p 2 + ⋯ + 2 p i
即:a k = a 2 p 1 × a 2 p 2 × ⋯ × a 2 p i a^k=a^{2^{p_1}}\times a^{2^{p_2}}\times\dots\times a^{2^{p_i}} a k = a 2 p 1 × a 2 p 2 × ⋯ × a 2 p i
对于a 2 0 × a 2 0 = a 2 1 , a 2 1 × a 2 1 = a 2 2 a^{2^0}\times a^{2^0}=a^{2^{1}},a^{2^{1}}\times a^{2^{1}}=a^{2^{2}} a 2 0 × a 2 0 = a 2 1 , a 2 1 × a 2 1 = a 2 2 ,即a 2 p i = a 2 p i − 1 × a 2 p i − 1 a^{2^{p_i}}=a^{2^{p_{i-1}}}\times a^{2^{p_{i-1}}} a 2 p i = a 2 p i − 1 × a 2 p i − 1
综上所述,在操作时记录a p i a^{p_i} a p i 的值,和累乘的结果
将k k k 化为二进制表示,按位>>
操作,若当前位是1 1 1 ,则对当前累乘的结果× a p i m o d p \times a^{p_i} \mod p × a p i mod p
每次对k k k 进行按位>>
操作后,更新a p i + 1 = a p i × a p i m o d p a^{p_{i+1}}=a^{p_i}\times a^{p_i}\mod p a p i + 1 = a p i × a p i mod p
当二进制下的k k k 无法再>>
时,累乘结果即为答案
模板
typedef long long LL;
LL qmi (LL a,LL k,LL p) {
LL res=1 ;
while (k){
if (k&1 ) res=res*a%p;
a=a*a%p;
k>>=1 ;
}
return res;
}
概念
同余:设m m m 为正整数,a a a 和b b b 是整数,若m ∣ a − b m|a-b m ∣ a − b ,则称a a a 模m m m 同余于b b b ,或a a a 与b b b 模m m m 同余,记作a ≡ b ( m o d m ) a\equiv b(mod~m) a ≡ b ( m o d m )
若a b ≡ 1 ( m o d m ) ab\equiv 1(mod~m) ab ≡ 1 ( m o d m ) ,则称b b b 为a a a 的模m m m 逆,记作a − 1 ( m o d m ) a^{-1}(mod~m) a − 1 ( m o d m ) 或a − 1 a^{-1} a − 1
注意
思想
模板例题 876. 快速幂求逆元
原题链接
描述
给定 n 组 ai,pi,其中 pi 是质数,求 ai 模 pi 的乘法逆元,若逆元不存在则输出 impossible。
注意:请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
若整数 b,m 互质,并且对于任意的整数 a,如果满足 b|a,则存在一个整数 x,使得 a/b≡a×x(modm),则称 x 为 b 的模 m 乘法逆元,记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b 的乘法逆元。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个数组 ai,pi,数据保证 pi 是质数。
输出格式
输出共 n 行,每组数据输出一个结果,每个结果占一行。
若 ai 模 pi 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible。
数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
LL qmi (LL a,LL k,LL p) {
LL res=1 ;
while (k){
if (k&1 ) res=res*a%p;
a=a*a%p;
k>>=1 ;
}
return res;
}
int main () {
int n;
cin >>n;
while (n--){
int a,p;
cin >>a>>p;
if (a%p==0 ) cout <<"impossible" <<endl ;
else cout <<qmi(a,p-2 ,p)<<endl ;
}
return 0 ;
}
思想
欧几里得算法:g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) g c d ( a , b ) = g c d ( b , a % b ) ,特别的g c d ( a , 0 ) = a gcd(a,0)=a g c d ( a , 0 ) = a
裴蜀定理:对于任意正整数a , b a,b a , b ,一定存在非零的x , y x,y x , y ,使得a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b )
{ b = 0 时 : { g c d ( a , b ) = a a x + b y = g c d ( a , b ) ⇒ { x = 1 y = 0 b ≠ 0 时: { ① 设 a x + b y = g c d ( a , b ) = d ∵ 由欧几里得算法可知: g c d ( a , b ) = g c d ( b , a % b ) = d ∴ 由裴蜀定理得: b x ′ + ( a % b ) y ′ = d 又 ∵ a x + b y = d ∴ 联立 { a x + b y = d b x ′ + ( a % b ) y ′ = d a % b = a − ⌊ a b ⌋ b ⇒ { x = y ′ y = x ′ − ⌊ a b ⌋ y ′ ② 设 a ′ = b , b ′ = a % b ∴ g c d ( b , a % b ) = g c d ( a ′ , b ′ ) = d ∵ g c d ( a ′ , b ′ ) = g c d ( b ′ , a ′ % b ′ ) = d ∴ b ′ x ′ ′ + a ′ % b ′ y ′ ′ = d 又 ∵ b x ′ + ( a % b ) y ′ = d ∴ 联立 { b x ′ + ( a % b ) y ′ = d b ′ x ′ ′ + a ′ % b ′ y ′ ′ = d a ′ % b ′ = a ′ − ⌊ a ′ b ′ ⌋ b ′ ⇒ { x ′ = y ′ ′ y ′ = x ′ ′ − ⌊ a ′ b ′ ⌋ y ′ ′ ③ 设 a ′ ′ = b ′ , b ′ ′ = a ′ % b ′ … … 直到 b = 0 时,联立解得 { x i = 1 y i = 0 然后逐步返回每一次联立所得的结果 { x i − 1 = y i y i − 1 = x i − ⌊ a i b i ⌋ y i 最后返回得到 x 和 y 的值
\begin{cases}
b=0时:\begin{cases}
gcd(a,b)=a\\ax+by=gcd(a,b)\\
\end{cases}\Rightarrow\begin{cases}x=1\\y=0\end{cases}
\\
\\
\\
\\
\\
b\neq0时:
\begin{cases}
\begin{aligned}
①&设~ax+by=gcd(a,b)=d\\
&\because 由欧几里得算法可知:gcd(a,b)=gcd(b,a\%b)=d\\
&\therefore 由裴蜀定理得:b{x}'+(a\%b){y}'=d\\
又&\because ax+by=d\\
&\therefore联立
\begin{cases}
ax+by=d\\b{x}'+(a\%b){y}'=d\\a\%b=a-\lfloor\frac{a}{b}\rfloor b
\end{cases}\Rightarrow\begin{cases}x={y}'\\y={x}'-\lfloor\frac{a}{b}\rfloor{y}'\end{cases}\\
②&设{a}'=b,{b}'=a\%b\\
&\therefore gcd(b,a\%b)=gcd({a}',{b}')=d\\
&\because gcd({a}',{b}')=gcd({b}',{a}'\%{b}')=d\\
&\therefore {b}'{x}''+{a}'\%{b}'{y}''=d\\
又&\because b{x}'+(a\%b){y}'=d\\
&\therefore联立\begin{cases}
b{x}'+(a\%b){y}'=d\\{b}'{x}''+{a}'\%{b}'{y}''=d\\{a}'\%{b}'={a}'-\lfloor\frac{{a}'}{{b}'}\rfloor{b}'
\end{cases}\Rightarrow\begin{cases}{x}'={y}''\\{y}'={x}''-\lfloor\frac{{a}'}{{b}'}\rfloor{y}''
\end{cases}\\
③&设{a}''={b}',{b}''={a}'\%{b}'\\
&\dots\\
&\dots\\
&直到b=0时,联立解得\begin{cases}{x}^i=1\\{y}^i=0\end{cases}\\
&然后逐步返回每一次联立所得的结果\begin{cases}{x}^{i-1}={y}^{i}\\{y}^{i-1}={x}^{i}-\lfloor\frac{{a}^{i}}{{b}^i}\rfloor{y}^{i}
&最后返回得到x和y的值
\end{cases}\\
\end{aligned}
\end{cases}
\end{cases}
⎩ ⎨ ⎧ b = 0 时 : { g c d ( a , b ) = a a x + b y = g c d ( a , b ) ⇒ { x = 1 y = 0 b = 0 时: ⎩ ⎨ ⎧ ① 又 ② 又 ③ 设 a x + b y = g c d ( a , b ) = d ∵ 由欧几里得算法可知: g c d ( a , b ) = g c d ( b , a % b ) = d ∴ 由裴蜀定理得: b x ′ + ( a % b ) y ′ = d ∵ a x + b y = d ∴ 联立 ⎩ ⎨ ⎧ a x + b y = d b x ′ + ( a % b ) y ′ = d a % b = a − ⌊ b a ⌋ b ⇒ { x = y ′ y = x ′ − ⌊ b a ⌋ y ′ 设 a ′ = b , b ′ = a % b ∴ g c d ( b , a % b ) = g c d ( a ′ , b ′ ) = d ∵ g c d ( a ′ , b ′ ) = g c d ( b ′ , a ′ % b ′ ) = d ∴ b ′ x ′′ + a ′ % b ′ y ′′ = d ∵ b x ′ + ( a % b ) y ′ = d ∴ 联立 ⎩ ⎨ ⎧ b x ′ + ( a % b ) y ′ = d b ′ x ′′ + a ′ % b ′ y ′′ = d a ′ % b ′ = a ′ − ⌊ b ′ a ′ ⌋ b ′ ⇒ { x ′ = y ′′ y ′ = x ′′ − ⌊ b ′ a ′ ⌋ y ′′ 设 a ′′ = b ′ , b ′′ = a ′ % b ′ … … 直到 b = 0 时,联立解得 { x i = 1 y i = 0 然后逐步返回每一次联立所得的结果 { x i − 1 = y i y i − 1 = x i − ⌊ b i a i ⌋ y i 最后返回得到 x 和 y 的值
注意
当方程符合a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 的形式时,才可以用扩展欧几里得算法求解( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 )
推论: 可以进一步求解任意方程a x + b y = n ax+by=n a x + b y = n ,得到一个整数解
{ ( 1 ) 判断方程 a x + b y = n 是否有整数解,有解的条件为: g c d ( a , b ) 可以整除 n ( 2 ) 用扩展欧几里得算法求 a x + b y = g c d ( a , b ) 得到一个解 ( x 0 , y 0 ) ( 3 ) 在 a x 0 + b y 0 = g c d ( a , b ) 两边同时乘 n g c d ( a , b ) ⇒ a x 0 n g c d ( a , b ) + b y 0 n g c d ( a , b ) = n ( 4 ) 对照 a x + b y = n 可知该方程的一个解为 ( x ′ , y ′ ) ,其中 { x ′ = x 0 n g c d ( a , b ) y ′ = y 0 n g c d ( a , b )
\begin{aligned}
\begin{cases}
&(1)~~判断方程ax+by=n是否有整数解,有解的条件为:gcd(a,b)可以整除n\\
&(2)~~用扩展欧几里得算法求ax+by=gcd(a,b)得到一个解(x_0,y_0)\\
&(3)~~在ax_0+by_0=gcd(a,b)两边同时乘\frac{n}{gcd(a,b)}\Rightarrow\frac{ax_0n}{gcd(a,b)}+\frac{by_0n}{gcd(a,b)}=n\\
&(4)~~对照ax+by=n可知该方程的一个解为({x}',{y}'),其中\begin{cases}{x}'=\frac{x_0n}{gcd(a,b)}\\{y}'=\frac{y_0n}{gcd(a,b)} \end{cases}
\end{cases}
\end{aligned}
⎩ ⎨ ⎧ ( 1 ) 判断方程 a x + b y = n 是否有整数解,有解的条件为: g c d ( a , b ) 可以整除 n ( 2 ) 用扩展欧几里得算法求 a x + b y = g c d ( a , b ) 得到一个解 ( x 0 , y 0 ) ( 3 ) 在 a x 0 + b y 0 = g c d ( a , b ) 两边同时乘 g c d ( a , b ) n ⇒ g c d ( a , b ) a x 0 n + g c d ( a , b ) b y 0 n = n ( 4 ) 对照 a x + b y = n 可知该方程的一个解为 ( x ′ , y ′ ) ,其中 { x ′ = g c d ( a , b ) x 0 n y ′ = g c d ( a , b ) y 0 n
模板
void exgcd (int a,int b,int &x,int &y) {
if (!b){
x=1 ,y=0 ;
return ;
}
else {
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
例题 877. 扩展欧几里得算法
原题链接
描述
给定 n 对正整数 ai,bi,对于每对数,求出一组 xi,yi,使其满足 ai×xi+bi×yi=gcd(ai,bi)。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含两个整数 ai,bi。
输出格式
输出共 n 行,对于每组 ai,bi,求出一组满足条件的 xi,yi,每组结果占一行。
本题答案不唯一,输出任意满足条件的 xi,yi 均可。
数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
void exgcd (int a,int b,int &x,int &y) {
if (!b){
x=1 ,y=0 ;
return ;
}
else {
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
int main () {
int n;
cin >>n;
while (n--){
int a,b,x,y;
cin >>a>>b;
exgcd(a,b,x,y);
cout <<x<<" " <<y<<endl ;
}
return 0 ;
}
概念
a x ≡ b ( m o d m ) ax\equiv b(mod~m) a x ≡ b ( m o d m ) ,即a x m \frac{ax}{m} m a x 与b m \frac{b}{m} m b 的余数相同,且a , b , m a,b,m a , b , m 为整数,求x x x 的值
该方程即为一元线性同余方程
思想
对a x ≡ b ( m o d m ) ax\equiv b(mod~m) a x ≡ b ( m o d m ) 做等价变形:a x + m y = b ax+my=b a x + m y = b
∵ a x ≡ b ( m o d m ) ∴ a x % m = k ( b % m ) , ( k ∈ Z ) ∴ a x − ⌊ a x m ⌋ m = k ( b − ⌊ b m ⌋ m ) ∴ a x − k b = ( ⌊ a x m ⌋ − k ⌊ b m ⌋ ) m ∵ ⌊ a x m ⌋ , ⌊ b m ⌋ , k ∈ Z ∴ ( ⌊ a x m ⌋ − k ⌊ b m ⌋ ) ∈ Z 设 ( ⌊ a x m ⌋ − k ⌊ b m ⌋ ) = y , ( y ∈ Z ) ∴ a x − k b = m y ⇒ a x − m y = b 又 ∵ y 可以为负数 ∴ a x ≡ b ( m o d m ) ↔ a x + m y = b
\begin{aligned}
&\because &ax&\equiv b(mod~m)\\
&\therefore &ax\%m&=k(b\%m),(k\in \Z)\\
&\therefore &ax-\lfloor\frac{ax}{m}\rfloor m&=k(b-\lfloor\frac{b}{m}\rfloor m)\\
&\therefore &ax-kb&=(\lfloor\frac{ax}{m}\rfloor-k\lfloor\frac{b}{m}\rfloor)m\\
&\because &\lfloor\frac{ax}{m}\rfloor,&\lfloor\frac{b}{m}\rfloor,k\in \Z\\
&\therefore &(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)\in \Z\\
&&设(\lfloor\frac{ax}{m}\rfloor&-k\lfloor\frac{b}{m}\rfloor)=y,(y\in \Z)\\
&\therefore &ax-kb&=my\Rightarrow ax-my=b\\
又&\because &y&可以为负数\\
&\therefore &ax\equiv b(mod~&m)\leftrightarrow ax+my=b
\end{aligned}
又 ∵ ∴ ∴ ∴ ∵ ∴ ∴ ∵ ∴ a x a x % m a x − ⌊ m a x ⌋ m a x − kb ⌊ m a x ⌋ , (⌊ m a x ⌋ 设 (⌊ m a x ⌋ a x − kb y a x ≡ b ( m o d ≡ b ( m o d m ) = k ( b % m ) , ( k ∈ Z ) = k ( b − ⌊ m b ⌋ m ) = (⌊ m a x ⌋ − k ⌊ m b ⌋) m ⌊ m b ⌋ , k ∈ Z − k ⌊ m b ⌋) ∈ Z − k ⌊ m b ⌋) = y , ( y ∈ Z ) = m y ⇒ a x − m y = b 可以为负数 m ) ↔ a x + m y = b
由扩展欧几里得算法的推论可知:当且仅当g c d ( a , m ) gcd(a,m) g c d ( a , m ) 可以整除b b b 时,a x + m y = b ax+my=b a x + m y = b 存在整数解
由扩展欧几里得算法可知: { 当 g c d ( a , m ) = b 时: { x = x 0 y = y 0 当 g c d ( a , m ) 为 b 的整数倍时: { x ′ = x 0 b g c d ( a , m ) y ′ = y 0 b g c d ( a , m )
由扩展欧几里得算法可知:
\begin{cases}
当gcd(a,m)=b时:\begin{cases}x=x_0\\y=y_0\end{cases}\\
当gcd(a,m)为b的整数倍时:\begin{cases}{x}'=\frac{x_0b}{gcd(a,m)}\\{y}'=\frac{y_0b}{gcd(a,m)}\end{cases}
\end{cases}
由扩展欧几里得算法可知: ⎩ ⎨ ⎧ 当 g c d ( a , m ) = b 时: { x = x 0 y = y 0 当 g c d ( a , m ) 为 b 的整数倍时: { x ′ = g c d ( a , m ) x 0 b y ′ = g c d ( a , m ) y 0 b
例题 878. 线性同余方程
原题链接
描述
给定 n 组数据 ai,bi,mi,对于每组数求出一个 xi,使其满足 ai×xi≡bi(modmi),如果无解则输出 impossible
。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一组数据 ai,bi,mi。
输出格式
输出共 n 行,每组数据输出一个整数表示一个满足条件的 xi,如果无解则输出 impossible
。
每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围
1≤n≤105,
1≤ai,bi,mi≤2×109
输出样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
void exgcd (LL a,LL b,LL &x,LL &y) {
if (!b){
x=1 ,y=0 ;
return ;
}
else {
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
}
LL gcd (LL a,LL b) {
return b ? gcd(b,a%b) : a;
}
int main () {
int n;
cin >>n;
while (n--){
LL a,b,m,x,y;
cin >>a>>b>>m;
LL d=gcd(a,m);
exgcd(a,m,x,y);
if (b%d) cout <<"impossible" <<endl ;
else cout <<b/d*x%m<<endl ;
}
return 0 ;
}
概念
若存在整数m 1 , m 2 , m 3 … m n m_1,m_2,m_3\dots m_n m 1 , m 2 , m 3 … m n 两两互质,则对于任意的整数a 1 , a 2 , a 3 … a n a_1,a_2,a_3\dots a_n a 1 , a 2 , a 3 … a n ,一元线性同余方程组( S ) (S) ( S ) 有通解
( S ) : { x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) x ≡ a 3 ( m o d m 3 ) … x ≡ a n ( m o d m n )
(S):
\begin{cases}
x\equiv a_1(mod~m_1)\\
x\equiv a_2(mod~m_2)\\
x\equiv a_3(mod~m_3)\\
\dots\\
x\equiv a_n(mod~m_n)\\
\end{cases}
( S ) : ⎩ ⎨ ⎧ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) x ≡ a 3 ( m o d m 3 ) … x ≡ a n ( m o d m n )
思想
对于( S ) (S) ( S ) 其中的两个式子进行合并
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⇒ { x = k 1 m 1 + a 1 x = k 2 m 2 + a 2
\begin{cases}
x\equiv a_1(mod~m_1)\\
x\equiv a_2(mod~m_2)\\
\end{cases}
\Rightarrow
\begin{cases}
x=k_1m_1+a_1\\
x=k_2m_2+a_2\\
\end{cases}
{ x ≡ a 1 ( m o d m 1 ) x ≡ a 2 ( m o d m 2 ) ⇒ { x = k 1 m 1 + a 1 x = k 2 m 2 + a 2
将等价转换后的两式进行联立,化简得k 1 m 1 + k 2 ( − m 2 ) = a 2 − a 1 ① k_1m_1+k_2(-m_2)=a_2-a_1~① k 1 m 1 + k 2 ( − m 2 ) = a 2 − a 1 ①
由扩展欧几里得算法可以得到一组解( k 1 ′ , k 2 ′ ) ({k_1}',{k_2}') ( k 1 ′ , k 2 ′ ) ,使得:k 1 ′ m 1 + k 2 ′ ( − m 2 ) = g c d ( m 1 , − m 2 ) {k_1}'m_1+{k_2}'(-m_2)=gcd(m_1,-m_2) k 1 ′ m 1 + k 2 ′ ( − m 2 ) = g c d ( m 1 , − m 2 )
若g c d ( m 1 , − m 2 ) gcd(m_1,-m_2) g c d ( m 1 , − m 2 ) 不能整除a 2 − a 1 a2-a1 a 2 − a 1 ,则无解,否则有通解
设g c d ( m 1 , − m 2 ) = d , y = ( a 2 − a 1 ) d gcd(m_1,-m_2)=d,y=\frac{(a_2-a_1)}{d} g c d ( m 1 , − m 2 ) = d , y = d ( a 2 − a 1 )
由扩展欧几里得算法的推论可知:{ k 1 = k 1 ′ y k 2 = k 2 ′ y \begin{cases}k_1={k_1}'y\\k_2={k_2}'y\end{cases} { k 1 = k 1 ′ y k 2 = k 2 ′ y
引入通解{ k 1 = k 1 + k m 2 d k 2 = k 2 + m 1 d \begin{cases}k_1={k_1}+k\frac{m_2}{d}\\k_2={k_2}+\frac{m_1}d\end{cases} { k 1 = k 1 + k d m 2 k 2 = k 2 + d m 1 ,k ∈ Z k\in \Z k ∈ Z
将通解带入① ① ① 得( k 1 + k m 2 d ) m 1 + ( k 2 + k m 1 d ) ( − m 2 ) = a 2 − a 1 ({k_1}+k\frac{m_2}{d})m_1+({k_2}+k\frac{m_1}{d})(-m_2)=a_2-a_1 ( k 1 + k d m 2 ) m 1 + ( k 2 + k d m 1 ) ( − m 2 ) = a 2 − a 1
化简得k 1 m 1 + k 2 ( − m 2 ) = a 2 − a 1 k_1m_1+k_2(-m_2)=a_2-a_1 k 1 m 1 + k 2 ( − m 2 ) = a 2 − a 1 和① ① ① 相同,故成立
重复上述步骤,不断合并剩余的式子,即可得到最终的通解
例题 204. 表达整数的奇怪方式
原题链接
描述
给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn,求一个最小的非负整数 x,满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式
第 1 行包含整数 n。
第 2…n+1 行:每 i+1 行包含两个整数 ai 和 mi,数之间用空格隔开。
输出格式
输出最小非负整数 x,如果 x 不存在,则输出 −1。
如果存在 x,则数据保证 x 一定在 64 位整数范围内。
数据范围
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
void exgcd (LL a,LL b, LL &x,LL &y) {
if (!b){
x=1 ,y=0 ;
return ;
}
else {
exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-a/b*y;
}
}
LL gcd (LL a,LL b) {
return b ? gcd(b,a%b) : a;
}
int main () {
int n;
cin >>n;
LL x=0 ,m1,a1;
cin >>m1>>a1;
for (int i=0 ;i<n-1 ;i++){
LL m2,a2;
cin >>m2>>a2;
LL k1,k2;
LL d=gcd(m1,m2);
exgcd(m1,m2,k1,k2);
if ((a2-a1)%d){
x=-1 ;
break ;
}
k1*=(a2-a1)/d;
k1=(k1%(m2/d)+m2/d)%(m2/d);
x=k1*m1+a1;
LL m=abs (m1/d*m2);
a1=k1*m1+a1;
m1=m;
}
if (x!=-1 ) x=(a1%m1+m1)%m1
cout <<x<<endl ;
return 0 ;
}
概念
初等行(列)变换
某一行乘上一个非零数,矩阵不变
某一行乘上一个常数加到另一行上,矩阵不变
交换矩阵中某两行的元素,矩阵不变
思想
对增广矩阵的每一列c i c_i c i 进行枚举,找到当前的列中绝对值最大的元素所在的行r i r_i r i
将r i r_i r i 行与最上方未确定阶梯型的行进行交换
用初等行变换将r i r_i r i 行变为原来的k k k 倍,且使得变换后, r i r_i r i 行的第一个数变成1 1 1
继续用初等行变换,将r i r_i r i 行下方的所有的行的c i c_i c i 列的值变为0 0 0
重复上述步骤,直到最终得到阶梯型矩阵,判断解的情况
若有解,则从最后一行向上回代,得出方程组的解
模板
const int N=110 ;
const double eps=1e-8 ;
int n;
double a[N][N];
int gauss () {
int c,r;
for (c=0 ,r=0 ;c<n;c++){
int t=r;
for (int i=r;i<n;i++){
if (fabs (a[i][c])>fabs (a[t][c])) t=i;
}
if (fabs (a[t][c])<eps) continue ;
if (t!=r) for (int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
for (int i=n;i>=c;i--) a[r][i]/=a[r][c];
for (int i=r+1 ;i<n;i++){
if (fabs (a[i][c])>eps){
for (int j=n;j>=c;j--) a[i][j]-=a[r][j]*a[i][c];
}
}
r++;
}
if (r<n){
for (int i=r;i<n;i++){
if (fabs (a[i][n])>eps) return 2 ;
}
return 1 ;
}
for (int i=n-1 ;i>=0 ;i--){
for (int j=i+1 ;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
}
return 0 ;
}
模板例题 883. 高斯消元解线性方程组
原题链接
描述
输入一个包含 n 个方程 n 个未知数的线性方程组。
方程组中的系数为实数。
求解这个方程组。
下图为一个包含 m 个方程 n 个未知数的线性方程组示例:
{ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 … a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b n
\begin{cases}
a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n=b_1\\
a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n=b_2\\
\dots\\
a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n=b_n\\
\end{cases}\\\\
⎩ ⎨ ⎧ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 … a m 1 x 1 + a m 2 x 2 + ⋯ + a mn x n = b n
输入格式
第一行包含整数 n。
接下来 n 行,每行包含 n+1 个实数,表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解,则输出共 n 行,其中第 i 行输出第 i 个未知数的解,结果保留两位小数。
如果给定线性方程组存在无数解,则输出 Infinite group solutions
。
如果给定线性方程组无解,则输出 No solution
。
数据范围
1≤n≤100,
所有输入系数以及常数均保留两位小数,绝对值均不超过 100。
输入样例:
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00
输出样例:
分析
由样例可 得增广矩阵: ( 1 2 − 1 − 6 2 1 − 3 − 9 − 1 − 1 2 7 ) c 1 中绝对 值最大元素位于 r 2 ,将 r 2 与 r 1 交换: ( 2 1 − 3 − 9 1 2 − 1 − 6 − 1 − 1 2 7 ) 将 r 1 的第 c 1 列元素变为 1 ,需要使得 r 1 × 1 2 : ( 1 0.5 − 1.5 − 4.5 1 2 − 1 − 6 − 1 − 1 2 7 ) 利用初等 行变换将 r 1 下方的所有的行的 c 1 列变为 0 : 即执行 r 2 − r 1 、 r 3 + r 1 ( 1 0.5 − 1.5 − 4.5 0 1.5 0.5 − 1.5 0 − 0.5 0.5 2.5 ) 此时 r 1 已 确定为阶梯矩阵的行,从 r 1 下方继续枚举 , c 2 中绝对 值最大的元素位于 r 2 ,由于 r 2 上方无未确 定的阶梯 矩阵的行,故不需要交换。 将 r 2 的第 c 2 列元素变为 1 ,需要使得 r 2 × 2 3 : ( 1 0.5 − 1.5 − 4.5 0 1 1 3 − 1 0 − 0.5 0.5 2.5 ) 利用初等 行变换将 r 2 下方的所有的行的 c 2 列变为 0 : 即执行 r 3 + r 2 × 1 2 ( 1 0.5 − 1.5 − 4.5 0 1 1 3 − 1 0 0 2 3 2 ) 此时 r 2 已 确定为阶梯矩阵的行,从 r 2 下方继续枚举 , r 3 为最后 一行,将 r 3 的第 c 3 列元素变为 1 ,需要使得 r 3 × 3 2 : ( 1 0.5 − 1.5 − 4.5 0 1 1 3 − 1 0 0 1 3 ) 判断该上 三角矩阵中不存在正对角线中某个元素为 0 , 此时 矩阵有唯 一解, x 3 = 3 , 从 r 2 进行回代 : 即执行 r 2 − r 3 × 1 3 ( 1 0.5 − 1.5 − 4.5 0 1 0 − 2 0 0 1 3 ) 此时可得 x 2 = − 2 , 回代 r 1 : 即执行 r 1 − r 2 × 1 2 + r 3 × 3 2 ( 1 0 0 1 0 1 0 − 2 0 0 1 3 ) 此时可得 x 1 = 1 , 综上可得 : { x 1 = 1 x 2 = − 2 x 3 = 3
\begin{aligned}
由样例可&得增广矩阵:\\\\
&\begin{pmatrix}
1&2&-1&-6\\
2&1&-3&-9\\
-1&-1&2&7\\
\end{pmatrix}\\\\c_1中绝对&值最大元素位于r_2,将r_2与r_1交换:\\\\
&\begin{pmatrix}
2&1&-3&-9\\
1&2&-1&-6\\
-1&-1&2&7\\
\end{pmatrix}\\\\
将r_1的第&c_1列元素变为1,需要使得r_1\times \frac{1}{2}:\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
1&2&-1&-6\\
-1&-1&2&7\\
\end{pmatrix}\\\\
利用初等&行变换将r_1下方的所有的行的c_1列变为0:\\
&即执行r_2-r_1、r_3+r_1\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
0&1.5&0.5&-1.5\\
0&-0.5&0.5&2.5\\
\end{pmatrix}\\\\
此时r_1已&确定为阶梯矩阵的行,从r_1下方继续枚举,\\
c_2中绝对&值最大的元素位于r_2,由于r_2上方无未确\\
定的阶梯&矩阵的行,故不需要交换。\\
将r_2的第&c_2列元素变为1,需要使得r_2\times \frac{2}{3}:\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
0&1&\frac{1}{3}&-1\\
0&-0.5&0.5&2.5\\
\end{pmatrix}\\\\
利用初等&行变换将r_2下方的所有的行的c_2列变为0:\\
&即执行r_3+r_2\times\frac{1}{2}\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
0&1&\frac{1}{3}&-1\\
0&0&\frac{2}{3}&2\\
\end{pmatrix}\\\\
此时r_2已&确定为阶梯矩阵的行,从r_2下方继续枚举,\\
r_3为最后&一行,将r_3的第c_3列元素变为1,需要使得r_3\times \frac{3}{2}:\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
0&1&\frac{1}{3}&-1\\
0&0&1&3\\
\end{pmatrix}\\\\
判断该上&三角矩阵中不存在正对角线中某个元素为0,此时\\
矩阵有唯&一解,x_3=3,从r_2进行回代:\\
&即执行r_2-r_3\times\frac{1}{3}\\\\
&\begin{pmatrix}
1&0.5&-1.5&-4.5\\
0&1&0&-2\\
0&0&1&3\\
\end{pmatrix}\\\\
此时可得&x_2=-2,回代r_1:\\
&即执行r_1-r_2\times\frac{1}{2}+r_3\times\frac{3}{2}\\\\
&\begin{pmatrix}
1&0&0&1\\
0&1&0&-2\\
0&0&1&3\\
\end{pmatrix}\\\\
此时可得&x_1=1,综上可得:
\begin{cases}
x_1=1\\x_2=-2\\x_3=3
\end{cases}
\end{aligned}
由样例可 c 1 中绝对 将 r 1 的第 利用初等 此时 r 1 已 c 2 中绝对 定的阶梯 将 r 2 的第 利用初等 此时 r 2 已 r 3 为最后 判断该上 矩阵有唯 此时可得 此时可得 得增广矩阵: ⎝ ⎛ 1 2 − 1 2 1 − 1 − 1 − 3 2 − 6 − 9 7 ⎠ ⎞ 值最大元素位于 r 2 ,将 r 2 与 r 1 交换: ⎝ ⎛ 2 1 − 1 1 2 − 1 − 3 − 1 2 − 9 − 6 7 ⎠ ⎞ c 1 列元素变为 1 ,需要使得 r 1 × 2 1 : ⎝ ⎛ 1 1 − 1 0.5 2 − 1 − 1.5 − 1 2 − 4.5 − 6 7 ⎠ ⎞ 行变换将 r 1 下方的所有的行的 c 1 列变为 0 : 即执行 r 2 − r 1 、 r 3 + r 1 ⎝ ⎛ 1 0 0 0.5 1.5 − 0.5 − 1.5 0.5 0.5 − 4.5 − 1.5 2.5 ⎠ ⎞ 确定为阶梯矩阵的行,从 r 1 下方继续枚举 , 值最大的元素位于 r 2 ,由于 r 2 上方无未确 矩阵的行,故不需要交换。 c 2 列元素变为 1 ,需要使得 r 2 × 3 2 : ⎝ ⎛ 1 0 0 0.5 1 − 0.5 − 1.5 3 1 0.5 − 4.5 − 1 2.5 ⎠ ⎞ 行变换将 r 2 下方的所有的行的 c 2 列变为 0 : 即执行 r 3 + r 2 × 2 1 ⎝ ⎛ 1 0 0 0.5 1 0 − 1.5 3 1 3 2 − 4.5 − 1 2 ⎠ ⎞ 确定为阶梯矩阵的行,从 r 2 下方继续枚举 , 一行,将 r 3 的第 c 3 列元素变为 1 ,需要使得 r 3 × 2 3 : ⎝ ⎛ 1 0 0 0.5 1 0 − 1.5 3 1 1 − 4.5 − 1 3 ⎠ ⎞ 三角矩阵中不存在正对角线中某个元素为 0 , 此时 一解, x 3 = 3 , 从 r 2 进行回代 : 即执行 r 2 − r 3 × 3 1 ⎝ ⎛ 1 0 0 0.5 1 0 − 1.5 0 1 − 4.5 − 2 3 ⎠ ⎞ x 2 = − 2 , 回代 r 1 : 即执行 r 1 − r 2 × 2 1 + r 3 × 2 3 ⎝ ⎛ 1 0 0 0 1 0 0 0 1 1 − 2 3 ⎠ ⎞ x 1 = 1 , 综上可得 : ⎩ ⎨ ⎧ x 1 = 1 x 2 = − 2 x 3 = 3
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=110 ;
const double eps=1e-8 ;
int n;
double a[N][N];
int gauss () {
int c,r;
for (c=0 ,r=0 ;c<n;c++){
int t=r;
for (int i=r;i<n;i++){
if (fabs (a[i][c])>fabs (a[t][c])) t=i;
}
if (fabs (a[t][c])<eps) continue ;
if (t!=r) for (int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
for (int i=n;i>=c;i--) a[r][i]/=a[r][c];
for (int i=r+1 ;i<n;i++){
if (fabs (a[i][c])>eps){
for (int j=n;j>=c;j--) a[i][j]-=a[r][j]*a[i][c];
}
}
r++;
}
if (r<n){
for (int i=r;i<n;i++){
if (fabs (a[i][n])>eps) return 2 ;
}
return 1 ;
}
for (int i=n-1 ;i>=0 ;i--){
for (int j=i+1 ;j<n;j++) a[i][n]-=a[j][n]*a[i][j];
}
return 0 ;
}
int main () {
cin >>n;
for (int i=0 ;i<n;i++){
for (int j=0 ;j<=n;j++){
cin >>a[i][j];
}
}
int t=gauss();
if (t==2 ){
cout <<"No solution" <<endl ;
}
else if (t==1 ) cout <<"Infinite group solutions" <<endl ;
else {
for (int i=0 ;i<n;i++){
if (fabs (a[i][n])<eps) a[i][n]=0 ;
printf ("%.2lf\n" ,a[i][n]);
}
}
return 0 ;
}
思想
模板例题 884. 高斯消元解异或线性方程组
原题链接
描述
输入一个包含 n 个方程 n 个未知数的异或线性方程组。
方程组中的系数和常数为 0 或 1,每个未知数的取值也为 0 或 1。
求解这个方程组。
异或线性方程组示例如下:
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
其中 ^ 表示异或(XOR),M[i][j] 表示第 i 个式子中 x[j] 的系数,B[i] 是第 i 个方程右端的常数,取值均为 0 或 1。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含 n+1 个整数 0 或 1,表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解,则输出共 n 行,其中第 i 行输出第 i 个未知数的解。
如果给定线性方程组存在多组解,则输出 Multiple sets of solutions。
如果给定线性方程组无解,则输出 No solution。
数据范围
1≤n≤100
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=110 ;
int n;
int a[N][N];
int guass () {
int c,r;
for (c=0 ,r=0 ;c<n;c++){
int t=r;
for (int i=r;i<n;i++){
if (a[i][c]) t = i;
}
if (!a[t][c]) continue ;
for (int i=c;i<=n;i++) swap(a[r][i],a[t][i]);
for (int i=r+1 ;i<n;i++){
if (a[i][c]){
for (int j=n;j>=c;j--) a[i][j]^=a[r][j];
}
}
r++;
}
if (r<n){
for (int i=r;i<n;i++){
if (a[i][n]) return 2 ;
}
return 1 ;
}
for (int i=n-1 ;i>=0 ;i--){
for (int j=i+1 ;j<n;j++){
a[i][n]^=a[i][j]*a[j][n];
}
}
return 0 ;
}
int main () {
cin >>n;
for (int i=0 ;i<n;i++){
for (int j=0 ;j<n+1 ;j++){
cin >>a[i][j];
}
}
int t=guass();
if (t==0 ){
for (int i=0 ;i<n;i++) cout <<a[i][n]<<endl ;
}
else if (t==1 ) cout <<"Multiple sets of solutions" <<endl ;
else cout <<"No solution" <<endl ;
return 0 ;
}
概念
从n n n 个不同元素中每次取出m m m 个不同元素,不管其顺序合成一组,称为从n n n 个元素中不重复地选取m m m 个元素的一个组合。
所有这样的组合的种数称为组合数
公式
C n m = n ! m ! ( n − m ) ! , C n 0 = C n n = 1 C_{n}^{m}=\frac{n!}{m!(n-m)!},C_n^0=C_n^n=1 C n m = m ! ( n − m )! n ! , C n 0 = C n n = 1
C n m = C n n − m C_n^m=C_n^{n-m} C n m = C n n − m
C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} C n m = C n − 1 m + C n − 1 m − 1
C n 0 + C n 1 + C n 2 + ⋯ + C n n = 2 n C_n^0+C_n^1+C_n^2+\dots+C_n^n=2^n C n 0 + C n 1 + C n 2 + ⋯ + C n n = 2 n
思想
C n m = C n − 1 m + C n − 1 m − 1 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} C n m = C n − 1 m + C n − 1 m − 1
递推公式求组合数
模板例题 885. 求组合数 I
给定 n 组询问,每组询问给定两个整数 a,b,请你输出 Cbamod(109+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一组 a 和 b。
输出格式
共 n 行,每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤2000
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=2010 ,mod=1e9 +7 ;
int c[N][N];
void init () {
for (int i=0 ;i<N;i++){
for (int j=0 ;j<=i;j++){
if (!j) c[i][j]=1 ;
else c[i][j]=(c[i-1 ][j]+c[i-1 ][j-1 ])%mod;
}
}
}
int main () {
init();
int n;
cin >>n;
while (n--){
int a,b;
cin >>a>>b;
cout <<c[a][b]<<endl ;
}
return 0 ;
}
思想
C n m = n ! m ! ( n − m ) ! = n ! × ( m ! ( n − m ) ! ) − 1 = n ! × m ! − 1 × ( n − m ) ! − 1 C_{n}^{m}=\frac{n!}{m!(n-m)!}=n!\times(m!(n-m)!)^{-1}=n!\times m!^{-1}\times (n-m)!^{-1} C n m = m ! ( n − m )! n ! = n ! × ( m ! ( n − m )! ) − 1 = n ! × m ! − 1 × ( n − m ) ! − 1
预处理fact[N]
和infact[N]
,fact[i]
存储i ! i! i ! ,infact[i]
存储i ! − 1 i!^{-1} i ! − 1
则C n m = C_n^m= C n m = fact[n]*infact[m]*infact[n-m]
预处理时利用快速幂求逆元( m o d 1 e 9 + 7 ) \pmod {1e9+7} ( mod 1 e 9 + 7 )
模板例题 886. 求组合数 II
原题链接
描述
给定 n 组询问,每组询问给定两个整数 a,b,请你输出 Cbamod(109+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一组 a 和 b。
输出格式
共 n 行,每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤105
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
const int N=1e5 +3 ,mod=1e9 +7 ;
LL fact[N],infact[N];
LL qmi (LL a,LL k,LL p) {
int res=1 ;
while (k){
if (k&1 ) res=res*a%p;
a=a*a%p;
k>>=1 ;
}
return res;
}
int main () {
fact[0 ]=infact[0 ]=1 ;
for (int i=1 ;i<N;i++){
fact[i]=fact[i-1 ]*i%mod;
infact[i]=infact[i-1 ]*qmi(i,mod-2 ,mod)%mod;
}
LL n;
cin >>n;
while (n--){
LL a,b;
cin >>a>>b;
cout <<fact[a]*infact[b]%mod*infact[a-b]%mod<<endl ;
}
return 0 ;
}
思想
模板例题
原题链接
描述
给定 n 组询问,每组询问给定三个整数 a,b,p,其中 p 是质数,请你输出 Cbamodp 的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一组 a,b,p。
输出格式
共 n 行,每行输出一个询问的解。
数据范围
1≤n≤20,
1≤b≤a≤1018,
1≤p≤105,
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
LL qmi (LL a,LL k,LL p) {
LL res=1 ;
while (k){
if (k&1 ) res=res*a%p;
a=a*a%p;
k>>=1 ;
}
return res;
}
LL C (LL a,LL b,LL p) {
if (b>a) return 0 ;
LL res=1 ;
for (LL i=1 ,j=a;i<=b;i++,j--){
res=res*j%p;
res=res*qmi(i,p-2 ,p)%p;
}
return res;
}
LL lucas (LL a,LL b,LL p) {
if (a<p&&b<p) return C(a,b,p);
return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main () {
int n;
cin >>n;
while (n--){
LL a,b;
LL p;
cin >>a>>b>>p;
cout <<lucas(a,b,p)<<endl ;
}
return 0 ;
}
思想
模板例题 888. 求组合数 IV
原题链接
描述
输入 a,b,求 Cba 的值。
注意结果可能很大,需要使用高精度计算。
输入格式
共一行,包含两个整数 a 和 b。
输出格式
共一行,输出 Cba 的值。
数据范围
1≤b≤a≤5000
输出样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=5010 ;
int primes[N];
int sum[N];
bool vis[N];
int cnt;
void get_primes (int n) {
for (int i=2 ;i<=n;i++){
if (!vis[i]) primes[cnt++]=i;
for (int j=0 ;primes[j]<=n/i;j++){
vis[primes[j]*i]=1 ;
if (i%primes[j]==0 ) break ;
}
}
}
int get (int n,int p) {
int res=0 ;
while (n){
res+=n/p;
n/=p;
}
return res;
}
vector <int > mul (vector <int > a,int b) {
vector <int > c;
int t=0 ;
for (int i=0 ;i<a.size();i++){
t+=a[i]*b;
c.push_back(t%10 );
t/=10 ;
}
while (t){
c.push_back(t%10 );
t/=10 ;
}
return c;
}
int main () {
int a,b;
cin >>a>>b;
get_primes(a);
for (int i=0 ;i<cnt;i++){
int p=primes[i];
sum[i]=get(a,p)-get(a-b,p)-get(b,p);
}
vector <int > res;
res.push_back(1 );
for (int i=0 ;i<cnt;i++){
for (int j=0 ;j<sum[i];j++){
res=mul(res,primes[i]);
}
}
for (int i=res.size()-1 ;i>=0 ;i--) cout <<res[i];
return 0 ;
}
思想
求S = S 1 ∪ S 2 ∪ S 3 S=S_1\cup S_2\cup S_3 S = S 1 ∪ S 2 ∪ S 3 的面积:
由图可知 : S = S 1 ∪ S 2 ∪ S 3 = S 1 + S 2 + S 3 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 3
\begin{aligned}
由图可知:S=&S_1\cup S_2\cup S_3\\
=&S_1+S_2+S_3\\
&-S_1\cap S_2-S_1\cap S_3-S_2\cap S_3\\
&+S_1\cap S_2\cap S_3
\end{aligned}
由图可知 : S = = S 1 ∪ S 2 ∪ S 3 S 1 + S 2 + S 3 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 3
推广求S = S 1 ∪ S 2 ∪ S 3 ∩ S 4 S=S_1\cup S_2\cup S_3\cap S_4 S = S 1 ∪ S 2 ∪ S 3 ∩ S 4 的面积:
S = S 1 ∪ S 2 ∪ S 3 ∩ S 4 = S 1 + S 2 + S 3 + S 4 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 1 ∩ S 4 − S 2 ∩ S 3 − S 2 ∩ S 4 − S 3 ∩ S 4 + S 1 ∩ S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 4 + S 1 ∩ S 3 ∩ S 4 + S 2 ∩ S 3 ∩ S 4 − S 1 ∩ S 2 ∩ S 3 ∩ S 4
\begin{aligned}
S=&S_1\cup S_2\cup S_3\cap S_4\\
=&S_1+S_2+S_3+S_4\\
&-S_1\cap S_2-S_1\cap S_3-S_1\cap S_4-S_2\cap S_3-S_2\cap S_4-S_3\cap S_4\\
&+S_1\cap S_2\cap S_3+S_1\cap S_2\cap S_4+S_1\cap S_3\cap S_4+S_2\cap S_3\cap S_4\\
&-S_1\cap S_2\cap S_3\cap S_4
\end{aligned}
S = = S 1 ∪ S 2 ∪ S 3 ∩ S 4 S 1 + S 2 + S 3 + S 4 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 1 ∩ S 4 − S 2 ∩ S 3 − S 2 ∩ S 4 − S 3 ∩ S 4 + S 1 ∩ S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 4 + S 1 ∩ S 3 ∩ S 4 + S 2 ∩ S 3 ∩ S 4 − S 1 ∩ S 2 ∩ S 3 ∩ S 4
若将面积作为集合看待,则容易推出:
设 U 中元素有 n 种不同的属性,而第 i 种属性称为 P i 拥有属性 P i 的元素构成集合 S i , 那么 ∣ ⋃ i = 1 n S i ∣ = ∑ i ∣ S i ∣ − ∑ i < j ∣ S i ∩ S j ∣ + ∑ i < j < k ∣ S i ∩ S j ∩ S k ∣ − … + ( − 1 ) m − 1 ∑ a i < a i + 1 ∣ ⋂ i = 1 m S a i ∣ + ⋯ + ( − 1 ) n − 1 ∣ S 1 ∩ ⋯ ∩ S n ∣ 即 : ∣ ⋃ i = 1 n S i ∣ = ∑ m = 1 n ( − 1 ) m − 1 ∑ a i < a i + 1 ∣ ⋂ i = 1 m S a i ∣
\begin{aligned}
&设U中元素有n种不同的属性,而第i种属性称为P_i拥有属性P_i的元素构成集合S_i,那么\\\\
&\begin{aligned}
\Bigg|\bigcup_{i=1}^{n}S_i\Bigg|=&\sum_i|S_i|-\sum_{i\lt j}|S_i\cap S_j|+\sum_{i\lt j\lt k}|S_i\cap S_j\cap S_k|-\dots\\
&+(-1)^{m-1}\sum_{a_i\lt a_{i+1}}\Bigg|\bigcap_{i=1}^mS_{a_i}\Bigg|+\dots+(-1)^{n-1}|S_1\cap\dots\cap S_n|\\
\end{aligned}\\\\&即:\\\\&\Bigg|\bigcup_{i=1}^{n}S_i\Bigg|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i\lt a_{i+1}}\Bigg|\bigcap_{i=1}^mS_{a_i}\Bigg|
\end{aligned}
设 U 中元素有 n 种不同的属性,而第 i 种属性称为 P i 拥有属性 P i 的元素构成集合 S i , 那么 ∣ ∣ i = 1 ⋃ n S i ∣ ∣ = i ∑ ∣ S i ∣ − i < j ∑ ∣ S i ∩ S j ∣ + i < j < k ∑ ∣ S i ∩ S j ∩ S k ∣ − … + ( − 1 ) m − 1 a i < a i + 1 ∑ ∣ ∣ i = 1 ⋂ m S a i ∣ ∣ + ⋯ + ( − 1 ) n − 1 ∣ S 1 ∩ ⋯ ∩ S n ∣ 即 : ∣ ∣ i = 1 ⋃ n S i ∣ ∣ = m = 1 ∑ n ( − 1 ) m − 1 a i < a i + 1 ∑ ∣ ∣ i = 1 ⋂ m S a i ∣ ∣
模板例题 890. 能被整除的数
原题链接
给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。
输入格式
第一行包含整数 n 和 m。
第二行包含 m 个质数。
输出格式
输出一个整数,表示满足条件的整数的个数。
数据范围
1≤m≤16,
1≤n,pi≤109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;
const int N=20 ;
int p[N];
int main () {
int n,m;
cin >>n>>m;
for (int i=0 ;i<m;i++) cin >>p[i];
LL res=0 ;
for (int i=1 ;i<1 <<m;i++){
LL t=1 ,s=0 ;
for (int j=0 ;j<m;j++){
if (i>>j&1 ){
if (t*p[j]>n){
t=-1 ;
break ;
}
t*=p[j];
s++;
}
}
if (t!=-1 ){
if (s%2 ) res+=n/t;
else res-=n/t;
}
}
cout <<res<<endl ;
return 0 ;
}
概念
若一个游戏满足:
由两名玩家交替行动
在游戏进行的任意时刻,可以执行的合法行动与轮到哪位玩家无关
不能行动的玩家判负
则称该游戏为一个公平组合游戏
尼姆游戏(NIM)属于公平组合游戏,但常见的棋类游戏,比如围棋就不是公平组合游戏,因为围棋交战双方分别只能落黑子和白子,胜负判定也比较负责,不满足条件2和3
游戏规则
给定n堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
例如:有两堆石子,第一堆有2个,第二堆有3个,先手必胜。
操作步骤
先手从第二堆拿走1个,此时第一堆和第二堆数目相同
无论后手怎么拿,先手都在另外一堆石子中取走相同数量的石子即可
思想
必胜状态 :先手进行某一个操作,留给后手是一个必败状态时,对于先手来说是一个必胜状态。即先手可以走到某一个必败状态
必败状态 :先手无论如何操作,留给后手都是一个必胜状态时,对于先手来说是一个必败状态。即先手走不到任何一个必败状态
结论 :假设有n n n 堆石子,数目分别是a 1 , a 2 , … , a n a_1,a_2,\dots,a_n a 1 , a 2 , … , a n ,如果a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1\oplus a_2\oplus\dots\oplus a_n\ne 0 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 ,先手必胜;否则先手必败。
证明
操作到最后时,每堆石子数都是0 0 0 ,即:0 ⊕ 0 ⊕ ⋯ ⊕ 0 = 0 0\oplus 0\oplus\dots\oplus0=0 0 ⊕ 0 ⊕ ⋯ ⊕ 0 = 0
在操作过程中,如果a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = x ≠ 0 a_1\oplus a_2\oplus\dots\oplus a_n=x\ne 0 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = x = 0 ,那么玩家必然可以通过拿走某一堆若干个石子将异或结果变为0 0 0
证明: 设 x 的二进制表示中最高一位 1 在第 k 位 则 a 1 , a 2 , … , a n 中,必然有一个数 a i ,它的第 k 为 1 且一定满足 : a i ⊕ x < a i 若从第 i 堆石子中拿走 ( a i − a i ⊕ x ) 个石子 则第 i 石子还剩 a i − ( a i − a i ⊕ x ) = = a i ⊕ x 个石子 由: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ … a n = x ≠ 0 可知 此时: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ x ⊕ … a n = x ⊕ x = 0
\begin{aligned}
证明:&\\
&设x的二进制表示中最高一位1在第k位\\
&则a_1,a_2,\dots,a_n中,必然有一个数a_i,它的第k为1\\
&且一定满足:a_i\oplus x\lt a_i\\
&若从第i堆石子中拿走(a_i−a_i\oplus x)个石子\\
&则第i石子还剩a_i−(a_i−a_i\oplus x)==a_i\oplus x个石子\\
&由:a_1\oplus a_2\oplus\dots\oplus a_i \oplus\dots a_n=x\ne 0可知\\
&此时:a_1\oplus a_2\oplus\dots\oplus a_i\oplus x \oplus\dots a_n=x\oplus x=0
\end{aligned}
证明: 设 x 的二进制表示中最高一位 1 在第 k 位 则 a 1 , a 2 , … , a n 中,必然有一个数 a i ,它的第 k 为 1 且一定满足 : a i ⊕ x < a i 若从第 i 堆石子中拿走 ( a i − a i ⊕ x ) 个石子 则第 i 石子还剩 a i − ( a i − a i ⊕ x ) == a i ⊕ x 个石子 由: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ … a n = x = 0 可知 此时: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ x ⊕ … a n = x ⊕ x = 0
在操作过程中,如果a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = x = 0 a_1\oplus a_2\oplus\dots\oplus a_n=x=0 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = x = 0 ,那么无论玩家怎么拿,必然会导致最终异或结果不为0 0 0
反证明: 假设玩家从第 i 堆石子拿走若干个,结果仍是 0 不妨设拿走后,第 i 堆还剩下 a ′ 个石子,且 a ′ < a i 此时仍有: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a ′ ⊕ … a n = 0 则有 ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a ′ ⊕ … a n ) = ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ … a n ) = a ′ ⊕ a i = 0 即: a ′ = a i ,与原假设 a ′ < a i 矛盾 故假设不成立
\begin{aligned}
反证明:&\\
&假设玩家从第i堆石子拿走若干个,结果仍是0\\
&不妨设拿走后,第i堆还剩下a'个石子,且a'\lt a_i\\
&此时仍有:a_1\oplus a_2\oplus\dots\oplus a'\oplus\dots a_n=0\\
&则有(a_1\oplus a_2\oplus\dots\oplus a'\oplus\dots a_n)=(a_1\oplus a_2\oplus\dots\oplus a_i\oplus\dots a_n)=a'\oplus a_i=0\\
&即:a'=a_i,与原假设a'\lt a_i矛盾\\
&故假设不成立
\end{aligned}
反证明: 假设玩家从第 i 堆石子拿走若干个,结果仍是 0 不妨设拿走后,第 i 堆还剩下 a ′ 个石子,且 a ′ < a i 此时仍有: a 1 ⊕ a 2 ⊕ ⋯ ⊕ a ′ ⊕ … a n = 0 则有 ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a ′ ⊕ … a n ) = ( a 1 ⊕ a 2 ⊕ ⋯ ⊕ a i ⊕ … a n ) = a ′ ⊕ a i = 0 即: a ′ = a i ,与原假设 a ′ < a i 矛盾 故假设不成立
综上:若先手面对的局面是a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n ≠ 0 a_1\oplus a_2\oplus\dots\oplus a_n\ne 0 a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n = 0 ,则先手必胜,反之先手必败
模板例题 891. Nim游戏
原题链接
描述
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜,则输出 Yes
。
否则,输出 No
。
数据范围
1≤n≤105,
1≤每堆石子数≤109
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
int main () {
int n;
cin >>n;
int res;
cin >>res;
for (int i=0 ;i<n-1 ;i++){
int m;
cin >>m;
res^=m;
}
if (res) cout <<"Yes" <<endl ;
else cout <<"No" <<endl ;
return 0 ;
}
原题链接
描述
现在,有一个 n 级台阶的楼梯,每级台阶上都有若干个石子,其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作,每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿)。
已经拿到地面上的石子不能再拿,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,其中第 i 个整数表示第 i 级台阶上的石子数 ai。
输出格式
如果先手方必胜,则输出 Yes
。
否则,输出 No
。
数据范围
1≤n≤105,
1≤ai≤109
输入样例:
输出样例:
分析
在采取最优策略的情况下,一方玩家对于偶数级台阶的操作的影响,可以被另一方玩家做相同操作的结果消去
故只考虑奇数级台阶的情况,适用于经典Nim
游戏
即:对于奇数级台阶,若先手面对的局面是a 1 ⊕ a 3 ⊕ ⋯ ⊕ a n ≠ 0 a_1\oplus a_3\oplus\dots\oplus a_n\ne 0 a 1 ⊕ a 3 ⊕ ⋯ ⊕ a n = 0 ,则先手必胜,反之先手必败
代码
#include <bits/stdc++.h>
using namespace std ;
int main () {
int n;
cin >>n;
int res;
cin >>res;
for (int i=2 ;i<=n;i++){
int m;
cin >>m;
if (i%2 ) res^=m;
}
if (res) cout <<"Yes" <<endl ;
else cout <<"No" <<endl ;
return 0 ;
}
游戏规则
给定n堆石子以及一个由k个不同正整数构成的数字集合S。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合S,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
核心思想
Mex运算: 设S S S 表示一个非负整数集合,定义M e x ( S ) Mex(S) M e x ( S ) 为求出不属于集合S S S 的最小自然数运算,例如:S = { 0 , 1 , 2 , 4 } S=\lbrace 0,1,2,4\rbrace S = { 0 , 1 , 2 , 4 } ,则M e s ( S ) = 3 Mes(S)=3 M es ( S ) = 3
S G SG SG 函数: 在有向图游戏中,对于每个节点x x x ,设从x x x 出发共有k k k 条有向边,分别到达节点y 1 , y 2 … y k y_1,y_2\dots y_k y 1 , y 2 … y k ,定义S G ( x ) SG(x) SG ( x ) 的后记节点y 1 , y 2 … y k y_1,y_2\dots y_k y 1 , y 2 … y k 的S G SG SG 函数值构成的集合在执行M e x Mex M e x 运算的结果,即:S G ( x ) = M e x ( { S G ( y 1 ) , S G ( y 2 ) … S G ( y k ) } ) SG(x)=Mex(\lbrace SG(y_1),SG(y_2)\dots SG(y_k)\rbrace) SG ( x ) = M e x ({ SG ( y 1 ) , SG ( y 2 ) … SG ( y k )}) ,特别地 ,整个有向图游戏G G G 的S G SG SG 函数值被定义为有向图游戏起点s s s 的S G SG SG 函数值,即 S G ( G ) = S G ( s ) SG(G)=SG(s) SG ( G ) = SG ( s )
S G SG SG 函数的性质:
定义终点的S G SG SG 函数值为0 0 0 ,
S G ( i ) = k , k ≠ 0 SG(i)=k,k\ne 0 SG ( i ) = k , k = 0 ,则i i i 最大能到达的点的S G SG SG 的范围为[ 0 , k − 1 ) [0,k−1) [ 0 , k − 1 )
若S G ( i ) = 0 SG(i)=0 SG ( i ) = 0 ,说明走不到0 0 0
有向图游戏的和: 若一个游戏的每个局面都可以构成一个有向图,则对于每个有向图的S G ( G 1 ) , S G ( G 2 ) … S G ( G n ) SG(G_1),SG(G_2)\dots SG(G_n) SG ( G 1 ) , SG ( G 2 ) … SG ( G n ) ,对所有图的S G SG SG 进行异或运算,即可得到该有向图游戏的和,且其结果满足Nim
游戏
S G SG SG 函数图解
根据每一步的不同选择生成路径单一的有向图,每条不同的路径对应不同的局面(方案)
定义终点的S G SG SG 函数值为0 0 0 ,倒推起点的S G SG SG 函数值
设一堆石子有10 10 10 个,每次操作可取的数量为S = { 2 , 5 } S=\lbrace 2,5\rbrace S = { 2 , 5 } ,无法操作即为终点,其S G SG SG 函数如下:
证明有向图游戏的和符合Nim游戏
操作到最后时,每一种局面的S G ( G i ) SG(G_i) SG ( G i ) 值都是0 0 0 ,即:0 ⊕ 0 ⊕ ⋯ ⊕ 0 = 0 0\oplus 0\oplus\dots\oplus0=0 0 ⊕ 0 ⊕ ⋯ ⊕ 0 = 0
在操作过程中,如果S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G n ) = x ≠ 0 SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x\ne 0 SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G n ) = x = 0 ,由S G SG SG 函数的性质可知,玩家必然可以走到某一局面将异或结果变为0 0 0
证明: 设 x 的二进制表示中最高一位 1 在第 k 位 则 S G ( G 1 ) , S G ( G 2 ) , … , S G ( G n ) 中,必然有一个局面 S G ( G i ) ,其值的第 k 为 1 且一定满足 : S G ( G i ) ⊕ x < S G ( G i ) 若将第 i 个局面的 S G 值取到 ( S G ( G i ) ⊕ x ) 由: S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G i ) ⊕ … S G ( G n ) = x ≠ 0 可知 此时: S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G i ) ⊕ x ⊕ … S G ( G n ) = x ⊕ x = 0
\begin{aligned}
证明:&\\
&设x的二进制表示中最高一位1在第k位\\
&则SG(G_1),SG(G_2),\dots,SG(G_n)中,必然有一个局面SG(G_i),其值的第k为1\\
&且一定满足:SG(G_i)\oplus x\lt SG(G_i)\\
&若将第i个局面的SG值取到(SG(G_i)\oplus x)\\
&由:SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i) \oplus\dots SG(G_n)=x\ne 0可知\\
&此时:SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)\oplus x \oplus\dots SG(G_n)=x\oplus x=0
\end{aligned}
证明: 设 x 的二进制表示中最高一位 1 在第 k 位 则 SG ( G 1 ) , SG ( G 2 ) , … , SG ( G n ) 中,必然有一个局面 SG ( G i ) ,其值的第 k 为 1 且一定满足 : SG ( G i ) ⊕ x < SG ( G i ) 若将第 i 个局面的 SG 值取到 ( SG ( G i ) ⊕ x ) 由: SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G i ) ⊕ … SG ( G n ) = x = 0 可知 此时: SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G i ) ⊕ x ⊕ … SG ( G n ) = x ⊕ x = 0
在操作过程中,如果S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G n ) = x = 0 SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x=0 SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G n ) = x = 0 ,那么无论玩家如何更改局面,必然会导致最终异或结果不为0 0 0
反证明: 假设玩家改变第 i 个局面的 S G 值,结果仍是 0 不妨设 S G ( G i ) 改变后的值为 S G ( G i ) ′ ,且 S G ( G i ) ′ < S G ( G i ) 此时仍有: S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G i ) ′ ⊕ … S G ( G n ) = 0 则有 ( S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G i ) ′ ⊕ … S G ( G n ) ) = ( S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G i ) ⊕ … S G ( G n ) ) = S G ( G i ) ′ ⊕ S G ( G i ) = 0 即: S G ( G i ) ′ = S G ( G i ) ,与原假设 S G ( G i ) ′ < S G ( G i ) 矛盾 故假设不成立
\begin{aligned}
反证明:&\\
&假设玩家改变第i个局面的SG值,结果仍是0\\
&不妨设SG(G_i)改变后的值为SG(G_i)',且SG(G_i)'\lt SG(G_i)\\
&此时仍有:SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)'\oplus\dots SG(G_n)=0\\
&则有(SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)'\oplus\dots SG(G_n))\\&=(SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_i)\oplus\dots SG(G_n))=SG(G_i)'\oplus SG(G_i)=0\\
&即:SG(G_i)'=SG(G_i),与原假设SG(G_i)'\lt SG(G_i)矛盾\\
&故假设不成立
\end{aligned}
反证明: 假设玩家改变第 i 个局面的 SG 值,结果仍是 0 不妨设 SG ( G i ) 改变后的值为 SG ( G i ) ′ ,且 SG ( G i ) ′ < SG ( G i ) 此时仍有: SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G i ) ′ ⊕ … SG ( G n ) = 0 则有 ( SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G i ) ′ ⊕ … SG ( G n )) = ( SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G i ) ⊕ … SG ( G n )) = SG ( G i ) ′ ⊕ SG ( G i ) = 0 即: SG ( G i ) ′ = SG ( G i ) ,与原假设 SG ( G i ) ′ < SG ( G i ) 矛盾 故假设不成立
综上:若先手面对的局面是S G ( G 1 ) ⊕ S G ( G 2 ) ⊕ ⋯ ⊕ S G ( G n ) = x ≠ 0 SG(G_1)\oplus SG(G_2)\oplus\dots\oplus SG(G_n)=x\ne 0 SG ( G 1 ) ⊕ SG ( G 2 ) ⊕ ⋯ ⊕ SG ( G n ) = x = 0 ,则先手必胜,反之先手必败,符合Nim
游戏
模板例题 893. 集合-Nim游戏
原题链接
描述
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 k,表示数字集合 S 中数字的个数。
第二行包含 k 个整数,其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数,其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式
如果先手方必胜,则输出 Yes
。
否则,输出 No
。
数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例:
输出样例:
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=1e6 +3 ;
int n,m;
int s[N],f[N];
int sg (int x) {
if (f[x]!=-1 ) return f[x];
set <int > vis;
for (int i=0 ;i<m;i++){
int sum=s[i];
if (x>=sum) vis.insert(sg(x-sum));
}
for (int i=0 ;;i++){
if (!vis.count(i)) return f[x]=i;
}
int main () {
cin >>m;
for (int i=0 ;i<m;i++) cin >>s[i];
cin >>n;
memset (f,-1 ,sizeof f);
int res=0 ;
for (int i=0 ;i<n;i++){
int x;
cin >>x;
res^=sg(x);
}
if (res) cout <<"Yes" <<endl ;
else cout <<"No" <<endl ;
return 0 ;
}
原题链接
描述
给定 n 堆石子,两位玩家轮流操作,每次操作可以取走其中的一堆石子,然后放入两堆规模更小的石子(新堆规模可以为 0,且两个新堆的石子总数可以大于取走的那堆石子数),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个整数,其中第 i 个整数表示第 i 堆石子的数量 ai。
输出格式
如果先手方必胜,则输出 Yes
。
否则,输出 No
。
数据范围
1≤n,ai≤100
输出样例:
输出样例:
分析
相比于集合-Nim
,这里的每一堆可以变成小于原来那堆的任意大小的两堆,即a[i]
可以拆分成(b[i],b[j])
为了避免重复,规定b[i]>=b[j]
,即:a[i]>b[i]>=b[j]
相当于一个局面拆分成了两个局面,由S G SG SG 函数理论,多个独立局面的S G SG SG 值,等于这些局面S G SG SG 值的异或和。因
此需要存储的状态就是sg(b[i])^sg(b[j])
代码
#include <bits/stdc++.h>
using namespace std ;
const int N=1e6 +3 ;
int n;
int f[N];
set <int > vis;
int sg (int x) {
if (f[x]!=-1 ) return f[x];
for (int i=0 ;i<x;i++){
for (int j=0 ;j<=i;j++){
vis.insert(sg(i)^sg(j));
}
}
for (int i=0 ;;i++){
if (!vis.count(i)) return f[x]=i;
}
}
int main () {
cin >>n;
memset (f,-1 ,sizeof f);
int res=0 ;
for (int i=0 ;i<n;i++){
int x;
cin >>x;
res^=sg(x);
}
if (res) cout <<"Yes" <<endl ;
else cout <<"No" <<endl ;
return 0 ;
}
I’m often to blogging and i really appreciate your content. The article has actually peaks my interest. I’m going to bookmark your web site and maintain checking for brand spanking new information.
This is my first time pay a quick visit at here and i am really happy to read everthing at one place
Good post! We will be linking to this particularly great post on our site. Keep up the great writing
Thanks for your supporting!
You’re so awesome! I don’t believe I have read a single thing like that before. So great to find someone with some original thoughts on this topic. Really.. thank you for starting this up. This website is something that is needed on the internet, someone with a little originality!