数论学习之起步篇（一）

1. 除法表达式（gcd法求最大公约数）

//直线上的点//求直线ax+by+c=0 上有多少个整点(x,y)满足x∈[x1,x2],y∈[y1,y2]。////扩展欧几里得算法，找出一对整数(x,y),使得ax+by=gcd(a,b)//递归实现： x1=y2; y1=x2-[a/b]*y2#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>using namespace std;int x,y,d;void ex_gcd(int a,int b){    if (!b)    {        x=1;        y=0;        return ;    }    ex_gcd(b,a%b);    int t = x;    x = y;    y = t - (a/b)*y;}void ex_gcd(int a, int b, int &d, int &x, int &y){    if (!b)    {        d=a;        x=1;        y=0;    }    else    {        ex_gcd(b,a%b,d,y,x);        y -= (a/b)*x;    }}int main (){    int a,b;    cin>>a>>b;    ex_gcd(a,b);    cout<<x<<" "<<y<<endl;    ex_gcd(a,b,d,x,y);    cout<<x<<" "<<y<<endl;    return 0;}其中x,y是ax+by=gcd(a,b)的一组解，(x+kb',y-ka')为任意解若ax+by=c，其中c是gcd(a,b)的倍数，那么有整数解，否则无整数解