Посчитать количество чисел, содержащих единицу, на промежутке [1; N]

сейчас подгоню. а что для 1е6 выдаёт?

dikiy(int n) правильно... я так понимаю, что косяк в том, что оно должно быть tmp + (m - 2) * (tmp - 1) + pow(10, n), щас попробую

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    if( m == 1) {
        /// Количество чисел с единичкой в промежутке [1; 10^n]
        return exp(n * log(10)) - exp(n * log(9)) + 1;
    } else {
        double tmp = dikiy(1, n);
        return tmp + (m - 2) * (tmp - 1) + pow(10,n) - 1;
    }
}

Вот теперь правильно. Проблема была в том, что если у нас 2000000, то числа 1****** все содержат единицу. Так-то.

Кстати, я не понял, как вывели это самое exp(n * log(10)) - exp(n * log(9))...

так. метод индукции, дедукции, пофигу. единиц в представлении одной цифрой - одна штука в представлении двумя (10..99): первая единичка - таких 10, плюс по одной из каждых предыдущих переборов с первой из оставшихся 2...9 - 8ми вариантов, значит 10..99 = 10 + 8. 1..99 = 18 + 1 представление 3мя (100...999): первая единичка: 100, 8 на представление 2-мя (т.е. на 18) плюс 1 (представление 1). 1...999 = 100 + 8*18 + 18 +1 = 100 + 9 * f(n-1) + 1

для представления f(N+1) 1*10^N = 1* f(N) + 9*f(N-1) +1 где-то такая рекурсивная функция у меня получилась. тогда F(ABCD) = F(1000) + (A-1)*F(100) + F(100) + (B-1) F(10) + F(10) + (C-1) F(1) + F(D) ну и можно упростить.

в каждой позиции может быть одно из 10 символов. 0..9

всего значит в N позициях может быть 10^N вариантов.

и мы знаем, что в позиции может быть или 1 или оставшиеся 9 символов.

размещая в N ячейках какой-либо из 9 символов, у нас будет 9^N комбинаций. значит разница между одним набором и другим такая, что в оставшихся вариантах будет присутствовать 10-ый символ.

10^N - 9^N в результате. чтобы не перегружать машины, можно вычислять экспоненциально (хотя толку от этого мало).

exp( n ln(10)) = exp ( ln (10^N)) = 10 ^N.

#include <iostream>
#include <cmath>
#include <cassert>

using namespace std;

/// Количество чисел с единичкой в промежутке [1; m*10^n]
int dikiy(int m, int n)
{
    assert(m >= 0);
    assert(n >= 0 && n < 10);
    if(m == 0) {
        return 0;
    } else if(n == 0) {
        return 1;
    } else if(m == 1) {
        return exp(n * log(10)) - exp(n * log(9)) + 1;
    } else {
        double tmp = dikiy(1, n);
        return tmp + (m - 2) * (tmp - 1) + pow(10,n) - 1;
    }
}

/// Количество чисел с единичкой в промежутке [1; x]
int fuckingFunc(int x)
{
    assert(x > 0);
    int result = 0;
    for (int i = log10(x); i >= 0; --i) {
        int tmp = x/pow(10,i);
        x -= tmp*pow(10,i);
        result += dikiy(tmp, i);
        if (tmp == 1) {
            /* если текущая цифра -- 1, добавляем остаток к результату и всё,
             * ведь при реальном счёте всё в остатке начиналось бы на 1 */
            result += x;
            break;
        }

    }
    return result;
}

int main()
{
    int x;
    do {
        cout << "Enter fucking positive number: ";
        cin >> x;
    } while(x < 1);
    
    int result = fuckingFunc(x);
    
    cout << "Your answer is " << result << ", dumbass." << endl;
}

Вот. Работает. Насчёт if (tmp == 1) пояснить, или и так понятно? Всем спасибо!.