简单数学板子和例题

发布于：2025-05-25 ⋅ 阅读:(19) ⋅ 点赞:(0)

线性丢番图方程

ax+by=c
d=gcd(a,b)，若c|d，有无穷整数解 $x=x_0+{b\over d}n,y=y_0-{a\over d}n$

POJ 1265

poj真难用，abs一直报错，万能头也不能用，给我调红温了

struct point
{
    int x,y;
} q[1010];
int n;
ll num,In;
double S;
int gcd(int A,int B)
{
    return B==0?A:gcd(B,A%B);
}
int Mult(point A,point B)
{
    return A.x*B.y-B.x*A.y;
}
int main()
{
    int T,xx,yy,sx,sy,dx,dy,K=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        sx=sy=0;
        S=0;
        num=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&xx,&yy);
            sx+=xx;
            sy+=yy;
            q[i].x=sx;
            q[i].y=sy;
        }
        q[0].x=q[n].x;
        q[0].y=q[n].y;
        for(int i=0; i<n; i++)
        {
            S+=Mult(q[i],q[i+1]);
            dx=abs(q[i].x-q[i+1].x);
            dy=abs(q[i].y-q[i+1].y);
            num+=gcd(max(dx,dy),min(dx,dy));
        }
        S=fabs(S/2);//不确定S是否为正数
        In=int(S)+1-num/2;//pick定理：点阵中 面积 = 内部格点数 + 边界格点数/2 - 1
        printf("Scenario #%d:\n",++K);
        printf("%I64d %I64d %.1f\n\n",In,num,S);
    }
    return 0;
}

扩展欧几里得算法

给 $a x + b y = c$ 找到一个特解

const int N=3e6+10;
int inv[N];
void solve(){
    int n,p;
    cin>>n>>p;
    inv[1]=1;
    cout<<inv[1]<<endl;
    forr(i,2,n){
        inv[i]=(p-p/i)*inv[p%i]%p;
        cout<<inv[i]<<endl;
    }
}

求逆

模意义下的乘法逆元

递推求1~n的模p的逆
$1^{-1}=1 \\ 若p/k=i...r，那么ki+r\equiv 0(mod\ \ p)\\ (p/i)r^{-1}+i^{-1}\equiv 0(mod\ \ p)\\ i^{-1}\equiv -(p/i)r^{-1}(mod\ \ p)\\ i^{-1}\equiv (p-p/i)r^{-1}(mod\ \ p)$

const int N=3e6+10;
int inv[N];
void solve(){
    int n,p;
    cin>>n>>p;
    inv[1]=1;
    cout<<inv[1]<<endl;
    forr(i,2,n){
        inv[i]=(p-p/i)*inv[p%i]%p;
        cout<<inv[i]<<endl;
    }
}

gcd

P1029最大公约数和最小公倍数问题

$x y = PQ, g c d (P, Q) = x, l c m (P, Q) = y$
给出xy，求出P Q对数
枚举

void solve()
{
    int x,y;cin>>x>>y;
    int a=x*y;
    int ans=0;
    for(int i=1;i*i<=a;i++){//枚举P Q
        if(a%i==0&&__gcd(i,a/i)==x)ans+=(i==a/i?1:2);//注意完全平方数 是一个情况
    }
    cout<<ans<<endl;
}

P10426

裴属定理

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

P4549

$A_1x_1+A_2x_2+A_3x_3=k\gcd(A_1,A_2)+A_3x_3=k'\gcd(A_1,A_2,A_3)$

void solve()
{
    int n;cin>>n;
    vector<int>a(n+1);
    forr(i,1,n){
        cin>>a[i];
    }
    int s=0;
    s=__gcd(a[1],a[2]);
    for(int i=3;i<=n;i++){
        s=__gcd(a[i],s);
    }
    cout<<abs(s)<<endl;
}

素数

位运算

P1469

相同的数两两异或得0

void solve()
{
    int n;cin>>n;
    int ans=0;
    forr(i,1,n){
        int a;cin>>a;
        ans=ans^a;
        // cout<<ans<<' ';
    }
    cout<<ans<<endl;
}