两个都是麻烦的计数问题,只不过一个是二进制,另一个似乎更贴近十进制的现实世界.不过计算机里,还是二进制感觉能跑得更快一些,移位总比乘十来得更快一些.
计数从0-n的每一位的数字个数,先计数位数小于n的位数的数字个数,再从高位到低位依次循环累加计数和n位数相同且小于n的数的各位数字.考虑的情形很多,有一点考虑不到就很难得到正确答案.
/**//*Source Code
Problem: 2282 User: y09shendazhi
Memory: 220K Time: 16MS
Language: C++ Result: Accepted
Source Code */
#include <iostream>
using namespace std;
int ans[15];//answer
int pow(int a,int b)
{
int an=1;
for(int i=0;i<b;i++)
an*=a;
return an;
}
void solve(int n)
{
int i,j,k;
memset(ans,0,sizeof(ans));
if(n<10)
{
for(i=1;i<=n;i++)
ans[i]=1;
return ;
}
int digit[20]={0};
int dec=0;//decimal of n
int temp=0;
temp=n;
while(temp)
{
digit[dec++]=temp%10;
temp/=10;
}
temp=pow(10,dec-1);
for(i=1;i<10;i++)//位数小于n的
ans[i]+=(dec-1)*temp/10;
ans[0]+=(dec-1)*temp/10-(temp-1)/9;
for(i=1;i<digit[dec-1];i++)//最高位是 1~最高位
{
ans[i]+=temp;
for(k=0;k<10;k++)
ans[k]+=(dec-1)*temp/10;
}
temp/=10;
for(i=dec-2;i>=0;i--)
{
for(j=0;j<digit[i];j++)
{
for(k=dec-1;k>i;k--)
ans[digit[k]]+=temp;
ans[j]+=temp;
for(k=0;k<10;k++)
ans[k]+=i*temp/10;
}
temp/=10;
}
for(i=0;i<dec;i++)
ans[digit[i]]++;
}
int main(int argc, char *argv[])
{
int n,m;
int ans1[15]={0};
int temp=0;
while(cin>>n>>m)
{
if(n==0 && m==0)
break;
if(n>m)
{
temp=n;
n=m;
m=temp;
}
solve(n-1);
memcpy(ans1,ans,sizeof(ans));
solve(m);
for(int i=0;i<9;i++)
cout<<ans[i]-ans1[i]<<' ';
cout<<ans[9]-ans1[9]<<endl;
}
return 0;
}
/**//*Source Code
Problem: 3252 User: y09shendazhi
Memory: 136K Time: 0MS
Language: C++ Result: Accepted
Source Code */
#include <iostream>
using namespace std;
// /n\
// | |
// \m/
__int64 com(__int64 n ,__int64 m)
{
if(n<m)
return 0;
__int64 result=1;
m=m<n-m?m:n-m;
for(__int64 i=1;i<=m;i++)
result=(result*(n-m+i))/i;
return result;
}
__int64 sumCom(__int64 n,__int64 m)
{
if(n==0 && m>=0)
return 1;
if(m>n)
m=n;
if(m<0)
return 0;
__int64 ans=0;
for(__int64 i=0;i<=m;i++)
{
ans+=com(n,i);
}
return ans;
}
__int64 solve(__int64 n)
{
if(n==0 || n==1)
return 0;
__int64 ans=0;
__int64 dec=0;//二进制位数
__int64 temp=n;
while(temp)
{
dec++;
temp>>=1;
}
temp=1;
temp<<=dec-1;
__int64 one=0;
for(__int64 j=1;j<dec;j++)
ans+=sumCom(j-1,j/2-1);
temp>>=1;
one++;
for(__int64 i=dec-1;i>0;i--)
{
if(temp&n)
{
ans+=sumCom(i-1,dec/2-one);
one++;
}
temp>>=1;
}
if(one<=dec/2)
ans++;
return ans;
}
int main()
{
__int64 S,F;
scanf("%I64d%I64d",&S,&F);
{
if(S==0)
printf("%I64d\n",solve(F));
else
printf("%I64d\n",solve(F)-solve(S-1));
}
return 0;
}