Bachelor 1-nの間にはいくつかの1があります
題意:数N(1<=N<=2147483647)を入力します.1-Nの間にいくつかの1があることを求めて、例えば:N=12、1の個数は5で、1の数字が現れるのはそれぞれ1,10,11,12です
コード:
コード:
#include <stdio.h>
__int64 find(__int64 n)
{
__int64 end = 1;
if (n == 0)
return 0;
if (n < 10)
return 1;
while (n >= end * 10)
end *= 10;
if (n / end == 1)
return n / end*find(end - 1) + (n%end + 1) + find(n%end);
// 1 , 1 1 ;
else
return n / end*find(end - 1) + end + find(n%end);
// 1 1 , end ;
}
int main()
{
__int64 n;
while (scanf("%I64d", &n) != EOF)
{
printf("%I64d
", find(n));
}
return 0;
}