数论学习之起步篇（一）
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)的倍数，那么有整数解，否则无整数解