Question

C++求很大数的阶乘问题

老师留了一道题，求1！的后六位+2！的后六位+3！的后六位……+100000！的后六位的和。请问各位大神怎么办啊

Answer 1

一下，具体我没做过。

先写一个大数乘法函数，输入输出全是字符串。
然后，用二分法。比如求50000的开平方，
先试5000/2=2500，2500*2500>5000，于是
试 2500/2=1250, 1250*1250>5000, 于是
试 1250/2=625, ……
……
试 156/2=78, 78*78>5000, 于是
试 78/2=39, 39*39<5000, 于是可以定位在39-78之间，
试（39+78)/2=57, 57*57<5000, 于是可以定位在57-78之间，
试 （57+78）/2=67，67*67<5000,于是可以定位在67-78之间，
试 （67+78）/2=72, 72*72>5000, 于是可以定位在67-72之间
……
最后定位在70-71之间，至于取哪个，看你怎么选了。

这是我写的一个求阶乘的函数，不知道对你有没有帮助。

#include <stdio.h>
#include <math.h>

#define LEN 1000

void multi_string(char *data_s1, char *data_s2, char *data_product);
void multi_string_single(char *data_s, char ch, char *data_sum);
void add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum);
int ctoi(char ch);
char itoc(int data);
void shift_left(char *data, int num);
void factorial(int order, char *pro_result);

/*=========================================================================*/

int ctoi(char ch)
{
switch(ch)
{
case '0' : return 0;
case '1' : return 1;
case '2' : return 2;
case '3' : return 3;
case '4' : return 4;
case '5' : return 5;
case '6' : return 6;
case '7' : return 7;
case '8' : return 8;
case '9' : return 9;
default : return 0;
}

}

char itoc(int data)
{
switch(data)
{
case 0 : return '0';
case 1 : return '1';
case 2 : return '2';
case 3 : return '3';
case 4 : return '4';
case 5 : return '5';
case 6 : return '6';
case 7 : return '7';
case 8 : return '8';
case 9 : return '9';
default : return '0';
}
}

/*=========================================================================*/

void multi_string_single(char *data_s, char ch, char *data_pro)
{
int times;
int i,j,k;
int len, len_0;
int len_pro_0;
int sum_tmp;
int carry;
int add_bits;

len = 0;
len_0 =0;
len_pro_0 = 0;

times = ctoi(ch);

while(data_s[len_0]=='0')
while(data_pro[len_pro_0]=='0')

while(data_s[len]!='\0')

for(i=0;i<LEN;i++)

/* begin to add*/
carry = 0;
sum_tmp = 0;
add_bits = 0;
for(k=0;k<times;k++)
{
carry = 0;
for(i=0;i<len - len_0 + add_bits;i++)
{
sum_tmp = ctoi(data_pro[LEN-1-i]) + ctoi(data_s[len-1-i]) + carry;
/* printf("\n%d = %d + %d + %d ; add_bits=%d\n" , sum_tmp, ctoi(data_pro[LEN-1-i]), ctoi(data_s[len-1-i]), carry , add_bits);}*/

data_pro[LEN-1-i] = itoc( sum_tmp % 10 );
carry = sum_tmp/10;
}

if(carry==1)

}

/* end adding */

return;
}

/*=========================================================================*/

void add_string(char *data_s1, char *data_s2, char *data_sum, int len_sum)
{

int i,j,k;
int carry;
int sum_tmp;
int len1,len2;
char data_s1_bit;
char data_s2_bit;

len1=0;
len2=0;

while(data_s1[len1]!='\0')
while(data_s2[len2]!='\0')

carry = 0;
for(i=0;i<len_sum;i++)
{
if(i>=len1) else
if(i>=len2) else

sum_tmp = ctoi(data_s1_bit) + ctoi(data_s2_bit) + carry;
data_sum[len_sum-1-i] = itoc( sum_tmp % 10 );
carry = sum_tmp/10;
}

return;
}

/*=========================================================================*/

void shift_left(char *data, int num)
{
int i;
int len;

len=0;
while(data[len]!='\0')

for(i=0;i<len;i++)
{
if(i<len-num)
else
}

return;
}

/*=========================================================================*/

void multi_string(char *data_s1, char *data_s2, char *data_product)
{
char data_pro_tmp[LEN+1];
char data_pro_single_tmp[LEN+1];
unsigned int len1_0, len2_0;
unsigned int len1, len2;
unsigned int len_pro;
int i,j,k;

len1_0 = 0;
len2_0 = 0;
len1 = 0;
len2 = 0;

while(data_s1[len1_0]=='0')
while(data_s2[len2_0]=='0')

while(data_s1[len1]!='\0')
while(data_s2[len2]!='\0')

for(i=0;i<LEN;i++)
{
data_pro_tmp[i] = '0';
data_pro_single_tmp[i] = '0';
}
data_pro_tmp[i] = '\0';
data_pro_single_tmp[i] = '\0';

for(k=0;k<len2-len2_0;k++)
{
multi_string_single(data_s1, data_s2[len2-1-k], data_pro_single_tmp);

shift_left(data_pro_single_tmp, k);
add_string(data_pro_single_tmp, data_pro_tmp, data_pro_tmp, LEN);
}

for(i=0;i<LEN;i++)

return;
}

/*=========================================================================*/

void factorial(int order, char *pro_result)
{
int i,j;
char added_number[LEN+1];

pro_result[LEN] = '\0';
added_number[LEN] = '\0';

/* initial added_number */
for(i=0;i<LEN-1;i++)
added_number[LEN-1] = '1';
pro_result[i] = '1';

for(j=0;j<order;j++)
{
multi_string(added_number, pro_result, pro_result);
add_string(added_number, "1", added_number, LEN);
}

return;
}

main()
{
char pro_result[LEN+1];
char added_number[LEN+1];
int len;
int i,j,k;
int order;
char judge;

/* char s1[LEN+1] = "0000011199"; */
/* char s2[LEN+1] = "0000022299"; */

char s1[LEN+1] = "123456";
char s2[LEN+1] = "123456";
char s3[LEN+1];
char s4[LEN+1];

s1[LEN] = '\0';
s2[LEN] = '\0';
s3[LEN] = '\0';
s4[LEN] = '\0';
pro_result[LEN] = '\0';
added_number[LEN] = '\0';

/* multi_string(s1, s2, s3); printf("\n%s * %s = %s\n", s1, s2, s3); */

/* multi_string_single(s2, '9', s_pro); */
/* printf("\ns_pro = %s\n", s_pro); */

/* initial added_number */

order = 1;
judge = '';

while(1)
{
printf("\n\n###########################################\n");
printf("\nPlease input the factorial number (between 1 and 400): ");
scanf("%d",&order);

if(order>=0 && order <=400)
{
factorial(order,s4);

printf("\n%d! = ", order);
k=0;
while(s4[k]=='0')
while(s4[k]!='\0')
printf("\n\n");

/*printf("\n%d! = %s\n\n", order, s4); */

}
else
{
printf("\nPlease input the correct number (between 1 and 100)!\n\n");
}

printf("Press q to exit, Press c to continue: ");
scanf("%s",&judge);
if(judge=='q'||judge=='Q')

}

if(judge!='q' && judge!='Q')
{ printf("\n\nPress Enter to exit.\n");
getch();
}

}
另外,站长团上有产品团购,便宜有保证

Answer 2

楼上用到了6位数乘以6位数，还是溢出了。
可以考虑用楼上的方法，将每一步化为6位数*6位数，把每个6位数分为1000a+b,
(1000a+b)*(1000c+d)其中1000000ac直接舍去，只要1000ad+1000bc+bd就不怕溢出了。

Answer 3

#include <stdio.h>

void main()
{
int i;
int result = 0;
int tmp = 1;

for (i = 1; i <= 100000; i++)
{
tmp = (tmp * i) % 1000000; //得到后6位
result += tmp;
}

printf("结果为%d\n", result);
}