求“自守数”程序优化

Question

“自守数” 是平方尾数等于该数自身的自然数。例如：

2525=625 7676=5776 9376*9376=87909376；
输入：n（自守数的位数）(n <= 15)；输出：n 位的自守数

当n>5时超出运行时间限制

如何优化程序，使当n较大时运行时间缩短？（以下是我写的程序）

#include<stdio.h>
#include<math.h> 
int main()
{
     int n;
    long long mul, number, k, a, b;
    scanf("%d",&n); 
    for( number=pow(10,n-1); number<pow(10,n); number++ )
    {
        for( mul=number, k=1; (mul/=10)>0; k*=10 );
        a = k * 10; 
        mul = 0;  
        b = 10; 
        while(k>0)
        {
            mul=( mul + ( number%(k*10) )*( number%b - number%(b/10) ) )%a;
            k /= 10;
            b *= 10;
        }
        if(number == mul) 
            printf("%lld\n", number);
    }
    return 0;
 
}

Answer 1

想到3个
第一个 for( mul=number, k=1; (mul/=10)>0; k*=10 );这句话是不是多余，在循环外面用pow算下值，这里n是知道的
第二个 平方的之后末尾只会出现 0 1 4 5 6 9 ， 2 3 7 8末尾的可以直接pass掉 并且这里只有可能末尾是1 5 6的数字
第三个 把平方换成多项式 取有效的数 比如25 * 25 =(20+5)^2 取有效位 20 * 5 * 2 + 5 * 5
可以在想想是否还有其它规律