质数
定义: 不讲了qwq...
性质: 对于一个足够大的整数N,不超过N的质数大约有
个.
试除法:
*若一个正整数N为合数,则存在一个能整除N的数T,其中
inline bool int prime(int n)
{
for(RN i=2;i<=sqrt(n);i++)
{
if(n%i==0)
return false;
}
return true;
}Miller-Robbin:
1.问题描述:
*测试一个正整数 p 是否为素数，需要较快且准确的测试方法。()
###费马小定理:
对于质数 p 和任意整数 a ，有
。
反之，若满足
将两边同时约去一个 a ，则有
。
也即是说：假设我们要测试 n 是否为质数。我们可以随机选取一个数 a ，然后计算
，如果结果不为 1 ，我们可以 100% 断定 n 不是质数。否则我们再随机选取一个新的数 a 进行测试。如此反复多次，如果每次结果都是 1 ，我们就假定 n 是质数.
二次探测定理:
如果 p 是奇素数，则
的解为 k≡1 或
即如果当我们用一个a费马小n后,看n是不是偶数,如果是,则取
,根据二次探测定理可知,即为k,则再判断&preview=true)
或&preview=true)
是否正确.若不成立,则不是质数.如果n是奇数,则直接跳过二次探测定理,用下一个a来费马.
几个 ai 的值： 2，3，5，7，11，61，13，17。用了这几个 ai，就连那个被称为强伪素数的 46856248255981 都能被除去.
单次测试失败的几率为 。那么假设我们做了 times 次测试，那么我们总错误的几率为
如果 times 为 20 次，那么错误概率约为 0.00000000000090949470 也就是意味着不可能发生的事件。
单次时间复杂度是 O(logn) ，总复杂度就是 O(times) 了。注意 long long 会爆，用 int128 就行了。
代码实现:
#define ll long long
ll p,a[]={2,3,5,7,11,61,13,17};
inline ll mul(ll a,ll b,ll mod)
{
ll ans=0;
for(ll i=b;i;i>>=1)
{
if(i&1) ans=(ans+a)%p;
a=(a<<1)%p;
}
return ans%p;
}
inline ll Pow(ll a,ll b,ll p)
{
ll ans=1;
for(ll i=b;i;i>>=1)
{
if(i&1) ans=mul(ans,a,p);
a=mul(a,a,p);
}
return ans%p;
}
inline bool Miller_Robbin(ll p)
{
if(p==2) return true;
if(p==1 || !(p%2)) return false;
ll d=p-1;int s=0;
while(!(d&1)) d>>=1,++s;
for(int i=0;i<=8 && a[i]<p;++i)
{
ll x=Pow(a[i],d,p),y=0;
for(int j=0;j<s;++j)
{
y=mul(x,x,p);
if(y==1 && x!=1 && x!=(p-1)) return false;
x=y;
}
if(y!=1) return false;
}
return true;
}Pollard-Rho 大合数分解:
算法流程:
先判断当前数N是否是素数（Miller_Rabin）了，如果是则直接返回。如果不是素数的话，试图找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。
算法解决:
那么,如何找到这个数的一个因子呢?对于一个大整数n,采用一种随机化算法,我们取任意一个数x使得x是n的质因数的几率很小,但如果取两个数x1以及x2使得它们的差是n的因数的几率就提高了.理论支撑:
生日悖论:
假设一年有 N 天，那么只要
存在相同生日的概率就已经大于 50% 了.即假如一个班级有58位同学,那么必定有两个同学的出生日期是相同的.正确性证明
利用伪随机数判断:
根据生日悖论,我们可以生成很多随机数相减法,与要求的N找最大公约数, 假设枚举的两个数为 i,j ，假设 i>j ，那么判断一下 gcd(i−j,n) 是多少，如果非 1 ，那么我们就已经找出了一个 n 的因子了，这样的概率随着枚举的组数变多会越来越大。但如果我们一开始就把所有的随机数都造出来,不仅内存储存不下,而且效率也不高,所以就有了以下生成伪随机函数:
f(x)=(x2+a)modn
inline int find_factorplus(int N) {
a = 2;
b = a;
do {
a = f(a);//a runs once
b = f(f(b));//b runs twice as fast
p = GCD( abs( b - a ) , N);
if( p > 1 ) return p;//Found factor: p
} while( b != a );
return 0;//Failed.
}一开始只需要两个数a,b,而且a可以rand也可以自己取(例如2),b可以根据随机函数生成.然而一般这种简单的随机数都会出现循环节，我们需要判断一下循环节.
###Floyd判环:
两个人同时在一个环形跑道上起跑，如果一个人是另外一个人的两倍速度，那么这个人绝对会追上另外一个人。追上时，意味着其中一个人已经跑了一圈了。
根据上面的结论,我们可以把b变成2倍速度a,如果发现有环,即a==b,那么跳出循环.寻找另外一个a.
inline int find_factorplus(int N) {
a = 2;
b = a;
do {
a = f(a);//a runs once
b = f(f(b));//b runs twice as fast
p = GCD( abs( b - a ) , N);
if( p > 1 ) return p;//Found factor: p
} while( b != a );
return 0;//Failed.
}Miller-Rabin 优化:
这个算法对于因子多，因子值小的数 n 是较为优异的。
也就是对于它的一个小因子 p ， Pollard−Rho 期望在 O() 时间内找出来。
但对于 n 是一个质数的情况，就没有什么较好的方法快速判断了，那么复杂度就是 O() 的。
此时就退化成暴力试除法了。
此时我们考虑用前面学习的 Miller−Rabin 算法来优化这个过程就行了。
代码实现:
#include<bits/stdc++.h>
using namespace std;
#define RI register int
#define LL long long
inline LL read()
{
LL res=0,f=1;
char ch=getchar();
while(ch!='-'&&(ch>'9'||ch<'0'))
ch=getchar();
if(ch=='-')
f=-1,ch=getchar();
while(ch>='0'&&ch<='9')
res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*f;
}
LL ans;
LL ksm(int x,LL p,LL Mod)
{
if(p==1)
return x%Mod;
LL res=ksm(x,p>>1,Mod);
res=(__int128)res*res%Mod;
if(p&1)
res=(__int128)res*x%Mod;
return res%Mod;
}
LL gcd(LL x,LL y)
{
return y?gcd(y,x%y):x;
}
inline bool mr0(int x,LL p)
{
if(ksm(x,p-1,p)!=1)
return false;
LL k=p-1;
while(!(k%2))
{
k>>=1;
LL t=(ksm(x,k,p)+p)%p;
if(t!=1&&t!=p-1)
return false;
if(t==p-1)
return true;
}
return true;
}
inline bool mr(LL x)
{
if(x==46856248255981||x<2)
return false;
if(x==2||x==3||x==7||x==61||x==24251)
return true;
return mr0(2,x)&&mr0(3,x)&&mr0(7,x)&&mr0(61,x)&&mr0(24251,x);
}
inline LL find(LL x)
{
LL t1=rand()%x,c=rand()%x,t2=((__int128)t1*t1+c)%x;;
LL dif=abs(t1-t2),cnt=0;
__int128 G=gcd(dif,x);
if(G>1)
return G;
while(true)
{
t1=((__int128)t1*t1+c)%x;
t2=((__int128)t2*t2+c)%x;
t2=((__int128)t2*t2+c)%x;
if(t1==t2)
return gcd(G,x);
dif=abs(t1-t2);
if(G*dif%x==0)
return gcd(G,x);
G=G*dif%x;
if(cnt%127==0)
{
LL r=gcd(G,x);
if(r>1)
return r;
cnt=1;
}
cnt++;
}
}
inline void PollardRho(LL x)
{
if(x==1||x<ans)
return;
if(mr(x))
{
if(x>ans)
ans=x;
return;
}
LL y=x;
while(y==x)
y=find(x);
PollardRho(y);
PollardRho(x/y);
}
int main()
{
srand((unsigned)time(NULL));
int T=read();
while(T--)
{
LL x=read();
ans=1;
if(mr(x))
{
printf("Prime\n");
continue;
}
PollardRho(x);
printf("%lld\n",ans);
}
return 0;
} 质数的筛选:
给定一个整数N,求出1~N之间的所有质数.
Eratosthenes 筛法:
任意整数x的倍数都不是质数.
时间复杂度O()
inline void prime(int x)
{
memset(v,o,sizeof(v));
for(RN i=1;i<=n;i++)
{
if(v[i]) continue;
cout<<i<<endl;
for(RN j=i;j<=n/i;j++)
v[i*j]=1;
}
}线性筛法:
从大到下累计质因子,让每一个数只有一种质因子产生方式
设数组V[]记录每个数的最小质因子.
1.依次考虑2~N之间每一个数i.
2.若v[i]=i,说明i是质数,把它保存下来.
3.扫描不大于v[i]的每个质数P,令v[i∗p]=p.也就是说在i的基础上累计一个质因子P,因为,所以p便是
的最小质因子.这样便能找出每一个数唯一的质因数分解方式.
时间复杂度O(N).
代码实现:
int v[maxn],prime[maxn];
inline void find(int n)
{
memset(v,0,sizeof(v));
for(RN i=2;i<=n;i++)
{
if(v[i])
continue;
cout<<i<<endl;
for(RN j=i;j<=n/i;j++)
v[i*j]=1;
}
}质因数分解:
基本定理:
任何一个大于1的正整数都能唯一分解为有限个质数的乘积.
其中
都是正整数,
都是质数,且满足
.
方法1 试除法:
inline void find(int n)
{
memset(c,0,sizeof(c));
m=0;
for(RN i=2;i*i<=n;i++)
{
if(n%i==0)
{
p[++m]=i;
while(n%i==0)
n/=i,c[m]++;
}
}
if(n>1)
{
p[++m]=n;
c[m]=1;
}
for(RN i=1;i<=m;i++)
{
cout<<p[i]<<"^"<<c[i]<<endl;
}
}
:
一个整数N的约数个数上界为
.
倍数法——求出1~N每个数的正约数集合:
概率与数学期望
样本点:随机实验的某种可能结果.
样本空间:所有可能结果所形成的集合.
随机事件:
随机变量:
概率:
定义:
博弈论:
NIM博弈
局面:游戏中面临的状态.
先手:整局游戏第一个行动的人.
后手:整局游戏第二个行动的人.
必败局面:若在某一局面下无论采取何种行动, 都会输掉游戏的局面.
必胜局面/最优策略:若在某一局面存在某种行动,使行动后对手面临必败局面.
NIM不存在平局,只有先手必胜和先手必败的两种情况.
定理:
NIM博弈先手必胜,当且仅当
京公网安备 11010502036488号