LevOJ P1468 高逐位整除数

前言：

我为什么要写这么一篇呢，因为我原本不想写的，找了半天都找不到源代码，花了我半小时（sad.jpg）和我一样懒的同志直接往下翻代码好了/doge

（学校的OJ，题目甚至有错别字，叹气.jpg）

分析题目，因为是高逐位整数，我们可以很方便的使用数组进行存储数字，需要进行运算的时候多用一步转换取出来就好

聪明的读者们肯定能一眼看出，这是典型的回溯问题，我也就不多加阐释了。但是我们需要注意，这里面有一点小小的容易出错的地方，我们注意到题目中最大位数是24位，然而我们c中long long int 变量能存储大概20位的长度，很容易溢出，这个时候我们就要寻求数学的帮助了。

我们给出324这么个数字

容易知道324%11 = 5；

由于知道这题会出现溢出，我们对这个数字进行一定的拆解：

3%11 = 3；

3*10+2 = 32 % 11 =10；

10*10+4 = 104 %11 = 5 我们惊奇的发现这样步步取模是可以避免溢出的，因此，我们只需要用int甚至不用long long int就能存下我们的数字（运算步骤中最大貌似是25*10+24吧，没仔细看）

当然，题主不会用数学的方法证明，只能找找规律用一用，如果有大佬会证，欢迎把链接放在下面

比心)

然后小细节我们放在代码的注释中，下面上代码:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <stdlib.h>#define ll long long int	
int a4[26] = { 0 };
void fun02(int length,int n)//这个length是递归的深度，最初传入深度0
{//显然n>=1if (n == 0)return;//没有上头这步运行程序，尝试数字26发现没有操作，说明最大符合要求的数字是25位// 因此添加以下边界条件if (n >= 26)return;//满足搜索边界条件，进行逐位输出操作if (length == n){if (a4[0] == 0)return;//第一位不能是0for (int i = 0; i < n; i++)printf("%d", a4[i]);printf("\n");}//不满足条件一位一位填充数字else {for (int i = 0; i <= 9; i++){a4[length] = i;ll temp = 0;//看到题主一开始没注意这么个问题，用了long long intlength += 1;for (int j = 0; j < length; j++)//算出前N位的数{temp = temp * 10 + a4[j];temp %= length;//取模防止溢出}if (temp == 0)//满足条件，进入下一层递归{fun02(length, n);length -= 1;//出来回溯，重新覆写上一个位置}else length -= 1;//不满足，重新覆写上一个位置}}}int main()
{int n;while (scanf("%d",&n) != EOF){fun02(0,n);}return 0;
}

后记：

受益的懒懒们点个赞叭(鞠躬