题解 | #自守数#

#include <stdio.h>
#include <string.h>

#define SIZE 10000
int arr[100];    //自守数数组

void getnum(int size);
int checknum(int num);

int main(void)
{
    getnum(SIZE);
    int num;
    
    while(scanf("%d",&num)!=EOF){
        printf("%d\n",checknum(num));
    }
    
    return 0;
}

void getnum(int size)
{
    int i,j,tmp;
    
    arr[0] = 1,arr[1] = 5,arr[2] = 6;    //前四个自守数易得
    for(i=7,j=3;i<=SIZE;i++){
        if(i<10) tmp = 10;
        else if(i<100) tmp = 100;
        else if(i<1000) tmp = 1000;
        else if(i<10000) tmp = 10000;
        else tmp = 100000;
        if((i*i - i) % tmp == 0){
            arr[j++] = i;    //记录自守数
        }
    }
}

int checknum(int num)
{
    int i = 0;        //因为要判断0，所以自守数数组内没有0，输出要+1多一个
    while(num >= arr[i] && arr[i]!=0) i++;
    return i+1;
}