首页 > 代码库 > 数论专题---除法表达式之高精度运算,扩展欧几里得算法

数论专题---除法表达式之高精度运算,扩展欧几里得算法

【题意描述】

给定这样一个表达式:X1/X2/X3/·····/Xk,其中Xi是正整数。除法表达式应到按照从左到右的顺序求和。但在表达式中嵌入括号可以改变计算顺序。输入表达式,判断是否可以通过加括号使得表达式最后的值为整数。

【分析】

表达式可以写成E=(X1·X3·····Xk)/X2;(X1一定在分子位置,X2一定在分母位置,其它任意)

问题变为E是否为整数。

对于大数相乘,我们可以采用两种方法避免数据溢出:

1.采用素数的唯一分解定理;存储可能存在素数的个数(如何存储,用一个数组就行)

2.采用公式直接约分的形式(用分子中的每一个数据和x2约分,如果最后x2能够变为1,那么表达式一定为整数,否则不为整数。

问题推广:

对于求a和b的最小公倍数如何求?(a和b都很大)

我们知道有这个公式:a*b=gcd(a,b)*lcm(a,b)

那么我们可以得到lcm(a,b)=a*b/gcd(a,b)。但是问题来了,a*b必定溢出。我们可以变换一种形式来写:lcm(a,b)=a/gcd(a,b)*b;那么数据就不会溢出了。

【题意描述】

求直线ax+by+c=0上有多少个整点(x,y)满足x在区间[x1,x2]且y在区间[y1,y2]内?

扩展欧几里得算法程序代码为:

void gcd(int a,int b,int &d,int &x,int &y){    if(!b) {d=a;x=1;y=0;}    else     {        gcd(b,a%b,d,y,x);        y-=x*(a/b);    }}

那么我们可以得到:

1.设a,b,c为任意整数。若方程ax+by=c的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb‘,y0-ka‘)。其中a‘=a/gcd(a,b),b‘=b/gcd(a,b)。k为任意整数。

2.设a,b,c为任意整数,g=gcd(a,b)。方程ax+by=g的一组整数解是(x0,y0)。则当c是g的倍数时ax+by=c有一组整数解(x0c/g,y0c/g).

数论专题---除法表达式之高精度运算,扩展欧几里得算法