算法举例
//自守数算法
例如：
25 ^ 2 = 625 76 ^ 2 = 5776 9376 ^ 2 = 87909376
例如：
376 被乘数 376 乘数 ------ --------- 2256 第一个部分积=被乘数*乘数的倒数第一位 2632 第二个部分积=被乘数*乘数的倒数第三位 1125 第三个部分积=被乘数*乘数的倒数第三位 -------- 141376
将以上的部分积的后3位求和后截取后3位就是3位数乘积的后3位。
C语言实现
1#include <stdio.h> 2 3/*由number的位数确定截取数字进行乘法时的系数k*/ 4#define forech_bit_num(mul,number,k) \ 5 for(mul=number,k=1;(mul/=10)>0;k*=10) ; 6//在0~xxxx这些数中寻找自守数 7#define forech_number(number,num) \ 8 for(number=0;number<num;number++) 9//自守数核心算法：(部分积+截取被乘数的后N位*截取乘数的第M位)，%kk再截取部分积 10#define automorphic_number(mul,number,k,ll,kk) \ 11 mul=(mul+(number%(k*10))*(number%ll-number%(ll/10)))%kk; 12long print_automorphic_number(long num) 13{ 14 long mul,number,k,ll,kk; 15 forech_number(number,num) 16 { 17 forech_bit_num(mul,number,k); 18 kk=k*10; /*kk为截取部分积时的系数*/ 19 mul=0; /*积的最后n位*/ 20 ll=10; /*ll为截取乘数相应位时的系数*/ 21 while(k > 0) 22 { 23 automorphic_number(mul,number , k ,ll ,kk); 24 k/=10; /*k为截取被乘数时的系数*/ 25 ll*=10; 26 } 27 if(number==mul){ /*判断若为自守数则输出*/ 28 printf("%ld ", number); 29 } 30 } 31 32} 33 34int main(void) 35{ 36 print_automorphic_number(1000); 37 return 0 ; 38}
运行结果:
