如何简单地求两个很大的数(10^10以上)的最大公约数
高手们,给点意见
#include<stdio.h> #include<string.h> void output(char * a, int an) { int i; for(i = an - 1; i >= 0; i--) putchar(a[i] + '0'); putchar('\n'); } void format(char * a, int an) { int i, j; char t; for(i = 0, j = an - 1; i < j; i++, j--) { a[i] -= '0'; a[j] -= '0'; t = a[i]; a[i] = a[j]; a[j] = t; } if(i == j) a[i] -= '0'; } void mul(char * a, int * an, char * b, int bn) { char t[256], s[256] = {0}; int i, j, k, f; for(i = 0; i < bn; i++) { if(b[i] == 0) continue; for(j = 0; j < i; t[j++] = 0); for(f = 0, k = 0; k < *an; k++) { t[j] = b[i] * a[k] + f; f = t[j] / 10; t[j++] %= 10; } if(f) t[j++] = f; for(f = 0, k = 0; k < j; k++) { s[k] += t[k] + f; if(s[k] >= 10){ s[k] -= 10; f = 1;} else f = 0; } if(f)s[j++] = 1; } for(i = 0; i < j; a[i] = s[i++]); *an = j; } void div(char * a, int * an, char * b, int bn) { char t[256], r[256] = {0}; int f, i, j; if(*an < bn) { a[0] = 0; a[1] = 0; *an = 1; return; } for(i = *an - bn; i >= 0; i--) { for(f = 0, j = 0; j < bn; j++) { t[j] = a[i + j] - b[j] - f; if(t[j] < 0){ t[j] += 10; f = 1;} else f = 0; } if(a[bn + i] - f >= 0) { a[bn + i] -= f; for(j = 0; j < bn; a[i + j] = t[j++]); r[i]++; i++; } } for(i = *an - bn; i && !r[i]; i--); for(j = i; j >= 0; a[j] = r[j--]); *an = i + 1; a[*an] = 0; } void mod(char * a, int * an, char * b, int bn) { if(*an<bn) return ; char c[101] = {0}; int i,j,k,low; for(i = *an-bn;i>=0;--i) { low = 0; for(j = 0;j<bn;++j) { c[j] = a[i+j] - b[j] - low; if(c[j]<0) {c[j] += 10;low = 1;} else low = 0; } if(a[i+bn] - low >= 0) { a[i+bn] -= low; for(k = 0;k<bn;++k) a[i+k] = c[k]; i++; } } for(i = bn-1;!a[i]&&i>=0;i--); *an = i+1; } void lcm(char *a, int * an, char *b, int bn) { char ta[256], tb[256], *pa, *pb, *pt; int pan, pbn, ptn, i; for(i = 0; i <= *an; ta[i] = a[i++]); for(i = 0; i <= bn; tb[i] = b[i++]); pa = ta; pb = tb; pan = *an; pbn = bn; mod(pa, &pan, pb, pbn); while(pan > 1 || pa[0]) { pt = pa; pa = pb; pb = pt; ptn = pan; pan = pbn; pbn = ptn; mod(pa, &pan, pb, pbn); } div(a, an, pb, pbn); mul(a, an, b, bn); } int main() { char a[256], b[256]; int an, bn; while(scanf("%s %s", a, b), a[0] > '0') { an = strlen(a); bn = strlen(b); format(a, an); format(b, bn); //mod(a, &an, b, bn); lcm(a, &an, b, bn); output(a, an); } return 0; }AC代码 留着当大数模板用吧