首页 > 代码库 > [蒟蒻修炼计划][学习笔记]数论(一)
[蒟蒻修炼计划][学习笔记]数论(一)
扩展欧几里得
求二元一次不定方程的一组解。
当时，有一组解
；
当时，因为
，
所以设满足
,
则 ,
整理得 。
所以。
就可以在求gcd的过程中得到一组解。
inline int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1;y=0;return a; } else{ int ret=exgcd(b,a%b,y,x); y-=a/b*x;return ret; }}
欧拉函数
欧拉函数的定义：小于等于
的正整数中与
互质的数的个数。
当时，
；
当时，
可以写成
个素数的幂的积的形式,第
个素数的质数为
:
根据容斥原理得，。
简单地推一下后发现，。
BSGS
求最小的使得
为质数。
令 ，则
，即
。
将所有的用
存起来，从小到大枚举
，直到
是某个
，
此时答案为。
由费马小定理可得，
，所以
,
所以可以用快速幂实现除法(时会有
)。
typedef long long ll; map<ll,ll> m;inline ll po(ll x,ll k,ll p){ ll ret=1; while(k){ if(k&1) ret=ret*x%p; x=x*x%p;k>>=1; } return ret;}inline ll bsgs(ll a,ll b,ll p){ if(gcd(a,p)!=1) return -1;
ll s=sqrt(p),k=1,x=1,y; while(s*s<=p) ++s; for(ll i=0;i<s;++i){ if(!m[k]) m[k]=i;
k=k*a%p; } for(ll i=0;i<s;++i){ y=b*po(x,p-2,p)%p; if(m.count(y)) return i*s+m[y]; x=x*k%p; } return -1;}
[蒟蒻修炼计划][学习笔记]数论(一)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。