奶牛的超十进制算数

题目

我们都知道，人类算术通常用十进制表示。但是奶牛可以超十进制表示一个正整数N，具体表示形式如下：

N=dk10k+dk-110k-1+...+d0100(dk≠0，并且对所有的i，di∈{0,1,2,...,10}

比如N=10有两种超十进制表示：10=10·100，和人类通常的十进制表示：10=1·101+0·100。

输入

多组测试数据，每组一行有一个正整数M(1≤M≤1016)。

输出

计算在区间[1,M]有多少个正整数可以有唯一的超十进制表示。对每组测试在单独一行中输出这个数。

Key：

唯一数：各个位上都不含有0. 例如234，先考虑200以内的唯一数 （2-1）*9*9+9*9+9=171； 再考虑百位固定为2的唯一数  （3-1 ）*9+4=22  171+22=193 

#include <iostream> #include <cstring> using namespace std; int main() { unsigned long long n; while(cin>>n) { unsigned long long p=n; int t=1,a[20]; unsigned long long sum=0,ans=0; memset(a,0,sizeof(a)); while(n!=0) //数组a用来记录各个位上的数字，t表示位数+1； { a[t]=n; t++; n/=10; } unsigned long long m=1; for(int i=t-2; i>=1; i--) { unsigned long long x=1; for(int j=1; j<=i; j++) { x*=9; } if(i==t-2) sum=sum+a[t-1]*x; else sum+=x; } for(int i=t-2;i>=1;i--) { if(a[i]==0) break; unsigned long long y=1; for(int j=1;j<i;j++) { y*=9; } if(i==1) sum=sum+a[i]*y; else sum=sum+(a[i]-1)*y; } if(p>=10) ans=sum; else ans=p; cout<<ans<<endl; } return 0; }