欧几里得算法

求两数的最大公约数,证明我不会就不写了


int gcd(int a, int b){
	return b == 0? a : gcd(b, a % b);
}

例题

UVA12716GCD等于XOR GCD XOR

异或的性质

1.若(a xor b=c)则(a xor c=b)

2.(a-b<=a xor b (a>=b))

设(a=k_1*c,b=k_2*c)

则(a-b=(k_1-k_2)*c)

则(a-b>=c)

因为上述性质2

所以(a-b<=c)

所以只要枚举(a)和(c),计算(b=a-c),则(gcd(a,b)=gcd(a,a-c)=c) 再验证是否有(c = a xor b)即可，时间复杂度为(O(nlogn)).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n,t;
const int N=30000001;
int ans[N];
int main() {
	for(int c=1;c<=N;++c)
	{
		for(int a=c+c;a<=N;a+=c)
		{
			int b=a-c;
			if(c==(a^b)) ans[a]++;
		}
	}
	for(int i=2;i<=N;++i)	ans[i]+=ans[i-1];
	cin>>t;
	for(int i=1;i<=t;++i)
	{
		n=read();
		cout<<"Case "<<i<<": "<<ans[n]<<'
';
	}
	return 0;
}

扩展欧几里得算法

扩展欧几里得算法，简称 $ exgcd $，一般用来求解不定方程，求解线性同余方程，求解模的逆元等。

求线性同余方程

方程如下

$ ax+by=gcd(a,b) $

(gcd(a,b)=gcd(b,a\%b))

所以可设 (a^,=b b^,=a \% b=a-a/b*b)

即方程变为 (a^,x+b^,y=gcd(a,b))

(b * x+(a-a/b * b) * y=gcd(a,b))

(y * a+(x-y * a/b) * b=gcd(a,b))

所以我们可以在欧几里得算法的基础上加上参数(x,y)来求解线性同于方程

void exgcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}

求线性同余方程的最小解

(ax+cy=b)的通解是(x+k * c/gcd(a,c))

我们令(p=c/gcd(a,c))

所以最小的整数解就是((x\%p+p)\%p)

注意要先加上(p)再模(p)

例题

POj2115神仙题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll A,B,C,k;
inline void exgcd(ll a,ll b,ll &g,ll &x,ll &y){
    if(b==0){x=1;y=0;g=a;}
    else{exgcd(b,a%b,g,y,x);y-=x*(a/b);}
}
int main(){
    while(scanf("%lld%lld%lld%lld",&A,&B,&C,&k)!=EOF){
        if(!A&&!B&&!C&&!k) break;
        ll c=B-A,a=C,b=1LL<<k,g,x,y;
        exgcd(a,b,g,x,y);
        if(c%g) printf("FOREVER
");
        else{
            b/=g;c/=g;
            printf("%lld
",(x%b*c%b+b)%b);
        }
    }
}

素数筛

埃氏筛((O(nloglogn)))

不解释了看图吧

for(int i=2;i<=t;i++) { 
	if(prime[i]) { 
		for(int j=2 * i;j<MAXN , j += i) 
		{ 
            prime[j]=false; 
   		} 
	}	 
}

欧拉筛((O(n)))

仔细看上面的动图你就会发现有些点被重复筛了

用一些办法是每个合数只会被它最小的质因子筛

用(vis[i])记录(i)的最小质因子

关于 if(i % prime[j] == 0) break

当 (i)是(prime[j])的倍数时，(i = k*prime[j])，如果继续运算 (j+1，i * prime[j+1] = prime[j] * k prime[j+1])，这里(prime[j])是最小的素因子，当(i = k * prime[j+1])时会重复，所以才跳出循环。

举个例子：(i = 8 ，j = 1，prime[j] = 2)，如果不跳出循环，(prime[j+1] = 3，8 * 3 = 2 * 4 * 3 = 2 * 12)，在(i = 12)时会计算。因为欧拉筛法的原理便是通过最小素因子来消除。

for(int i=2; i<=n; i++){ 
	if(!vis[i]) prime[cnt++]=i; 
	for(int j = 0; j < cnt && i * prime[j] <= n; j++){ 
		vis[i * prime[j]]=prime[j]; 
		if(i % prime[j] == 0) break; 
	} 
}