我把大数的乘除求余法给你
这个题目是中文的
http://www.
你自己去改
程序代码:
#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;
}