好像之前写过了，不过老师让写笔记就有写了一遍

简单数学

声明本文是用笔记本电脑的键盘写的误触的几率非常大所以可能会出现奇怪的问题

欧几里得算法

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

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_1c,b=k_2c$

则$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]<<'\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)$

$bx+(a-a/bb)*y=gcd(a,b)$

$ya+(x-ya/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\n");
        else{
            b/=g;c/=g;
            printf("%lld\n",(x%b*c%b+b)%b);
        }
    }
}

简单数学

原文：https://www.cnblogs.com/pyyyyyy/p/11317240.html