一 素数
今天先来回顾一下之前学过的素数（质数），当n是质数时，以下两个式子，至少有一个是成立的
1.a的d次方 % n == 1
2.存在一个i,0 <= i < r,a的d乘2的i次方的次方 % n == n - 1
那我们怎样用它判断素数呢？
如果\(n\)为质数 --- \(a\) --- 一定成立
如果\(n\)为合数 --- \(a\) --- 可能成立,可能不成立 --- 如果不成立,为合数 --- 如果成立,再算,再成立,再算 --- 如果一直成立,不保证100%,但是99.999% --- 要是错了,去买彩票吧...
总结就是，miller_rabin算法用了极其微小的正确率，换来了更加优秀的时间复杂度
#include<bits/stdc++.h>
using namespace std;
int ksm(int a,int b,int p){
if(b == 0) return 1%p;
int c=ksm(a,b/2,p);
c=1ll*c*c%p;
if(b % 2 == 1) c=1ll*c*a%p;
return c;
}
bool miller_rabin(int n,int a){//O(log n)
int d=n-1,r=0;
while(d % 2 == 0){
d=d/2;
r=r+1;
}
int v=ksm(a,d,n);
if(v == 1) return true;//若第一条满足，return ture
for(int i=0;i<r;i++){
if(v == n-1) return true;//若第二条满足，return true
v=(__int128)v*v%n;//没有必要写快速幂，不断的平方就好了
}
return false;
}
bool is_prime(int n){
if(n < 2) return false;
if(n == 2) return true;
for(int i=1;i<=20;i++){
int a=rand() % (n-1)+1;//赌徒，随机赋值
if(miller_rabin(n,a) == false) return false;
}
return true;
}
int prime_list[10]={2,3,5,7,11,13,17,19,31,97};
bool is_prime2(int n){
if(n < 2) return false;
for(int i=0;i<10;i++){
if(n == prime_list[i]) return true;
if(n % prime_list[i] == 0) return false;
if(miller_rabin(n,prime_list[i] % n) == false) return false;
}
return true;
}
signed main(){
int n;
cin>>n;
if(is_prime(n) == true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
if(is_prime2(n) == true) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
那如果换一种形式呢？现在，请你求出1$n$中的所有质数。可以将枚举1\(n\)，将i的所有倍数都标记为不是质数，你肯定会写出这样的一坨代码
int not_prime[1010];
void f(int n){//O(nloglog n)
for(int i=2;i<=n;i++){
if(not_prime[i] == false){
for(int j=i+i;j<=n;j+=i){
not_prime[j] = true;
}
}
}
}
可以看出，它的复杂度是O(nloglog n)，其实已经够用了，但我们还要继续优化——线性筛
#include<bits/stdc++.h>
using namespace std;wq
const int maxn=1000010;
int pcnt,not_prime[maxn],plist[maxn];
signed main(){
int n;
cin>>n;
not_prime[1] = true;
for(int i=1;i<=n;i++){
if(not_prime[i] == false){
pcnt=pcnt+1;
plist[pcnt] = i;
}
for(int j=1;j<=pcnt;j++){
int v=plist[j] * i;
if(v > n) break;
not_prime[v] = true;
if(i % plist[j] == 0){
break;
}
}
}
return 0;
}
二 组合数学
组合数学主要分为加法原理和乘法原理，他们两个的区别就是加法原理不可以同时选，而乘法原理可以同时选，具体看图
现在给你一道题，有n个人，从中选出m个人，而不同的顺序算不同的方案
可得出\(P(n,m)=n(n-1)(n-2)(n-3)(n-4)....(n-m)\)
很好，那如果不同的顺序算相同的方案呢
可得出\(\dfrac{P(n,m)}{m!}\)
相信聪明的你肯定还可以列出组合数的递推式
\(C(i,j) = C(i-1,j-1) + C(i-1,j)\)
有没有感觉这坨东西有点似曾相识，没错，这就是杨辉三角形，看下面
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
三 还是组合数学
在组合数学中，有一类很常见的题目，但他们又有一些其他的分类（待补充）
给定\(n,m,p\)，请你按照各题输出\(C(n,m)\%P\)
-
\(n,m \le 10^3,P \le 10^9\)：
由于数据范围不大，所以直接用递推式\(C(i,j) = C(i-1,j-1) + C(i-1,j)\)
signed main(){ int t,k; cin>>t>>k; for(int i=0;i<=200;i++){ c[i][0] = 1; for(int j=1;j<=i;j++){ c[i][j]=c[i-1][j-1]+c[i-1][j]; } } cout<<c[t][k]<<'\n'; return 0; } -
\(n,m \le 10^6,P \approx 10^9\)（\(P\) 为质数,有 \(q\) 次询问，\(q \le 10^6\)）：
可以用公式 \(C(n,m)= \dfrac{n!}{m!(n-m)!}\)。
signed main(){ fac[0] = 1; for(int i=1;i<=1000000;i++){ fac[i]=1ll*fac[i-1]*i%p; } for(int i=0;i<=1000000;i++){ ifac[i]=ksm(fac[i],p-2); } for(int i=1;i<=q;i++){ int n,m; cin>>n>>m; int ans=1ll*fac[n]*ifac[m]%p*ifac[n-m]%p; cout<<ans<<endl; } returen 0; } -
\(n \le 10^9,m \le 10^3,1 \le P \le 10^9\)(任意数)
可以用程序来实现约分
signed main(){ cin>>n>>m>>p; for(int i=1;i<=m;i++){ fenzi[i] = n-i+1; fenmu[i] = i; } for(int i=1;i<=m;i++){ for(int j=1;j<=m;j++){ int g=gcd(fenzi[i],fenmu[j]); fenzi[i] = fenzi[i] / g; fenmu[j] = fenmu[j] / g; } } int ans=1; for(int i=1;i<=m;i++){ ans=1ll*ans*fenzi[i]%p; } cout<<ans<<endl; return 0; } -
\(n,m \le 10^18,P \le 10^5,P\) 为质数，有 \(q\) 次询问（\(q \le 10^5\)）：
需要用到Lucas 定理（当 \(P\) 是质数时，$C(n,m) % P=C(n % P,m % P) \times C(n \div P,m \div P) % P $）。
int C(int n,int m){ if(n < p) return 1ll * fac[n] * ifac[m] % p *ifac[n-m] % p; else return 1ll * C(n%p,m%p) * C(n/p,m/p) % p; } signed main(){ fac[0] = 1; for(int i=1;i<=1000000;i++){ fac[i]=1ll*fac[i-1]*i%p; } for(int i=0;i<=1000000;i++){ ifac[i]=ksm(fac[i],p-2); } for(int i=1;i<=q;i++){ int n,m; cin>>n>>m; int ans=1ll*fac[n]*ifac[m]%p*ifac[n-m]%p; cout<<ans<<endl; } returen 0; }
四 抽屉原理
大概意思就是你先在有\(n+1\)个鼠标，还有\(n\)台电脑，把鼠标插到电脑上，那么肯定有一台电脑要插两个鼠标。这，就是抽屉原理
现在，给你一个数\(C\)，并给你\(N\)个数，从他们之中选出任意个数，使得他们的和是\(C\)的倍数。
那么，这和抽屉原理有什么关系呢？
我们可以把它看成一个序列，每一个数的位置都有一个前缀和，也就是有\(n\)个前缀和，把这\(n\)个前缀和放到\(n-1\)个抽屉里，那一个放两个的那段序列，就是最终的答案！
五 容斥原理
要想了解他，先看一道题。
给你一个数\(n\)，请问\(1-n\)中有多少个数可以表示成\(x ^ y,1 \le y\)
#include<bits/stdc++.h>
using namespace std;
int fac[70];
//fac[i] 代表 x^i这种数 被算了几次了
long long n;
int main()
{
cin >> n;//计算1-n中有多少个数可以表示成x^y,x>1,y>1的形式
long long ans=0;
for (int i=2;i<=64;i++)
{
long long v = floor(pow(n,1.0/i)) - 1;//计算2~n中有多少个数 可以表示成x^i的形式
int d = 1 - fac[i];//代表x^y这种 还应该被算几次
ans += d*v;
for (int j=i;j<=64;j+=i)
fac[j] += d;
}
cout << ans+1 << endl;
//输出时记得加上减去的 1
return 0;
}
六 组合数拆分P4369
现在有这样一道例题，给定你\(x\)和\(k\)，请你把\(x\)拆分成\(k\)个不同的组合数只和，请你输出任意一种方案。\(x \le 10^9 , k \le 10^3\)
#include <bits/stdc++.h>
using namespace std;
signed main(){
int x,k;
cin>>x>>k;
for (int i=1;i<k;i++){
cout<<i<<" "<<0<<'\n';
}
cout<<x-k+1<<" "<<1<<'\n';
return 0;
}