我自己也搞不清为什么分到组合数学里面去。一个找规律+递推的题目；才开始我也是理解错了题目以为求i位置下的数呢，题目要求的是第i个位置下的数字只能是0-----9了。WA了好几次才发现。
首先根据(（1 + x）*x)/2 = 2147483647 估算到达65537肯定超过2147483647各数字。所以只要计算1到65537的各位数字即可。
a[i]存第i行 1到i有多少个数字 sum[i]记录的是1 -- i 行总共有多少数字。首先根据sum确定i位置在那一行（按i分行,如下），然后在求在这一行的位置
1
1 2
1 2 3
1 2 3 4
.....
才开始不知到可以直接用log10(1.0*i) + 1求i的10进制书有多少位，所以我就分类枚举过得，后来游泳公式写了一下。
枚举的：
View Code #include#include #include #define maxn 65539using namespace std;long long a[maxn],sum[maxn],n;int main(){ //freopen("in.txt","r",stdin); int i,t; memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); for (i = 1; i < maxn; ++i) { a[i] = a[i - 1] + 1; if (i >= 10) a[i]++; if (i >= 100) a[i]++; if (i >= 1000) a[i]++; if (i >= 10000) a[i]++; } for (i = 1; i < maxn; ++i) sum[i] = sum[i - 1] + a[i]; scanf("%d",&t); while (t--) { scanf("%lld",&n); int pos; for (i = 0; i < maxn; ++i) { if (n > sum[i] && n <= sum[i + 1]) { pos = i + 1; break; } } //printf("POS = %d\n",pos); if (n == sum[pos]) { printf("%d\n",pos%10); } else { long long ct = sum[pos - 1]; //printf("<><><><%lld\n",ct); for (i = 1; i <= pos; ++i) { if (i >= 10 && i <= 99) { if (ct + 1 == n) { printf("%d\n",(i/10)%10); break; } else if (ct + 2 == n) { printf("%d\n",(i%10)); break; } else ct += 2; } else if (i >= 100 && i <= 999) { if (ct + 1 == n) { printf("%d\n",(i/100)%10); break; } else if (ct + 2 == n) { printf("%d\n",(i/10)%10); break; } else if (ct + 3 == n) { printf("%d\n",(i%10)); break; } else ct += 3; } else if (i >= 1000 && i <= 9999) { if (ct + 1 == n) { printf("%d\n",(i/1000)%10); break; } else if (ct + 2 == n) { printf("%d\n",(i/100)%10); break; } else if (ct + 3 == n) { printf("%d\n",(i/10)%10); break; } else if (ct + 4 == n) { printf("%d\n",(i%10)); break; } else ct += 4; } else if (i >= 10000 && i <= pos) { if (ct + 1 == n) { printf("%d\n",(i/10000)%10); break; } else if (ct + 2 == n) { printf("%d\n",(i/1000)%10); break; } else if (ct + 3 == n) { printf("%d\n",(i/100)%10); break; } else if (ct + 4 == n) { printf("%d\n",((i/10)%10)); break; } else if (ct + 5 == n) { printf("%d\n",(i%10)); break; } else ct += 5; } else { if (ct+ 1 == n) { printf("%d\n",i); break; } else ct++; //printf(">>>>%lld %d\n",ct,i); } } } } return 0;}
调用公式：
View Code #include#include #include #include #define maxn 65539using namespace std;long long a[maxn],sum[maxn],n;int main(){ //freopen("in.txt","r",stdin); int i,t; memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); for (i = 1; i < maxn; ++i) { a[i] = a[i - 1] + (int)log10(1.0*i) + 1; } //for (i = 1; i <= 20; ++i) printf("%d ",a[i]); //printf("\n"); for (i = 1; i < maxn; ++i) sum[i] = sum[i - 1] + a[i]; scanf("%d",&t); while (t--) { scanf("%lld",&n); int pos; for (i = 1; i < maxn; ++i) { if (n <= sum[i]) { pos = i; break; } } if (n == sum[pos]) { printf("%d\n",pos%10); continue; } int len = 0; int ct = n - sum[pos - 1]; //printf("%d %d\n",ct,pos); for (i = 1; len < ct; ++i) { len += ((int)log10(1.0*i) + 1); } //printf(">>%d\n",i); printf("%d\n",((i - 1)/(int)pow(10*1.0,1.0*(len - ct)))%10); } return 0;}