2.6学习
2.6.1
gcd
扩展欧几里得算法
模板如下，具体运算过程书上解释很清楚

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

例题实战
1.洛谷P1082 同余方程
a∗ x ≡ 1(modb) 推导
a∗ x mod b = 1
a∗ x = y∗ b + 1
a∗ x + y∗ b = 1
然后就是直接套板子了，记得是最小正整数
以及a∗ x ≡ 1(modb) 的用法
这位大佬的博客写的很详细 点击传送

#include <bits/stdc++.h>
using namespace std;
int extgcd(int a,int b,int &x,int &y)
{int d=a;if(b!=0){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1,y=0;}return d;
}
int main()
{int a,b,x,y;cin>>a>>b;extgcd(a,b,x,y);b=abs(b);while(x<0)x+=b;while(x-b>0)x-=b;cout<<x<<"\n";return 0;
}

2.P1516 青蛙的约会
emmm,收获是知道了AX+BY=C时，X的最小正解是运算过extgcd后，x=(x*(C/d)%(B/d)+B/d)%(B/d)
挺重要的，建议背诵（
上一题也可以直接用这个公式

#include <bits/stdc++.h>
using namespace std;
int extgcd(long long int a,long long int b,long long int &x,long long int &y)
{long long int d=a;if(b!=0){d=extgcd(b,a%b,y,x);y-=(a/b)*x;}else{x=1,y=0;}return d;
}
int main()
{long long int x,y,n,m,l;cin>>x>>y>>m>>n>>l;long long int a=x-y;long long int b=n-m;if(b<0){a=-a;b=-b;}long long int q,w;long long int c=extgcd(b,l,q,w);if(a%c==0)cout<<(q*(a/c)%(l/c)+l/c)%(l/c)<<"\n";elsecout<<"Impossible\n";return 0;
}

上一题的main函数部分也可以更改了

	int a,b,x,y;cin>>a>>b;int c=extgcd(a,b,x,y);
//	b=abs(b);
//	while(x<0)
//	x+=b;
//	while(x-b>0)
//	x-=b;cout<<(x*(1/c)%(b/c)+b/c)%(b/c)<<"\n";return 0;

2.6.2 有关素数的基础算法
单个素数处理，可以直接从1跑到

 整数分解 
map <int , int > prime_factor (int n) {map <int , int >ans ;for(int i = 2; i * i <= n; i ++) {while (n % i == 0) {++ ans [i];n /= i;}}if(n != 1) ans [n] = 1;return ans ;
}

枚举n以内的素数，埃式筛法，复杂度O（nloglogn)

int prime[MAX_N];//第i个素数 
bool is_prime[MAX_N+1];//素数为true
//返回n以内素数的个数
int sieve(int n)
{int p=0;for(int i=0;i<=n;i++){is_prime[i]=true;}is_prime[0]=is_prime[1]=false;for(int i=2;i<=n;i++){if(is_prime[i]){prime[p++]=i;for(int j=2*i;j<=n;j+=i){is_prime[j]=false;}}}return p;
}

区间筛法
求a<=x<b的素数个数

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int MAXN = 1000000+5;
bool is_prime[MAXN];
bool is_prime_small[MAXN];
void segment(ll a, ll b)
{// ------------初始化 --------------for(ll i=0; i*i<b; i++)is_prime_small[i] = true;for(ll i=0; i<b-a; i++)is_prime[i]=true;// ---------------------------------for(ll i=2; i*i<b; i++){if(is_prime_small[i]){// 筛[2,sqrt(b) for(ll j=(ll)2*i; j*j<b; j+=i)is_prime_small[j] = false;// 筛[a,b)for(ll j=max((a-1+i)/i,2ll)*i; j<b; j+=i)is_prime[j-a] = false;}}
}
int main()
{ll a, b;cin >> a >> b;segment(a, b);ll ans = 0;for(ll i=a; i<b; i++){if(is_prime[i-a])ans++;}cout << ans << endl;return 0;
}

快速幂
反复平方法
复杂度O(logn)

1号 
long long fact(long long a,long long b,int c)
{long long sum=1%c;for(;b;b>>=1){if(b&1)sum=sum*a%c;a=a*a%c;}return sum;
}
2号 
typedef long long ll;
ll mod_pos(ll x,ll n,ll mod) {//快速幂ll res=1;while(n>0) {if(n&1)res=res*x%mod;//如果2进制最低位为1，则乘上x^(2^i)x=x*x%mod;//将x平方n>>=1;}return res;
}
3号
ll mod_pos(ll x,ll n,ll mod)
{if(n==0) return 1;ll res=mod_pow(x*x%mod,n/2,mod);if(n&1) res=res*x%mod;return res;}