Данное в условии $$$z$$$-число назовëм просто $$$z$$$, его длину обозначим за $$$n$$$, а цифру, в каждом его разряде $$$d$$$.

Тогда несложно видеть, что при $$$2 \le n$$$ и $$$d \neq 1$$$ число $$$z$$$ имеет делитель $$$d$$$, подходящий под условие.

При $$$n = 1$$$, так как все однозначные числа являются $$$z$$$-числами, то нужно понять, есть ли у $$$z$$$ натуральный делитель кроме $$$1$$$ и самого себя, это так если $$$z$$$ является составным числом, то есть $$$4$$$, $$$6$$$, $$$8$$$ или $$$9$$$.

Наконец при $$$d = 1$$$ заметим, что $$$z$$$ делится на другое $$$z$$$-число вида $$$\overline{11...11}$$$ (пусть в нём $$$m$$$ единиц) тогда и только тогда когда $$$n$$$ кратно $$$m$$$. Это несложно доказать, например, по индукции.

В таком случае, если $$$n$$$ – составное число, то существует такое $$$m$$$ не равное $$$1$$$ и $$$n$$$, что $$$n$$$ делится на $$$m$$$ и тогда $$$z$$$ имеет делитель – число из $$$m$$$ единиц. Иначе, все делители $$$z$$$ вида $$$z$$$-чисел могут быть разве что однозначными, а для делимости на них достаточно проверить только делимость на простые однозначные, а именно $$$2$$$, $$$3$$$, $$$5$$$ и $$$7$$$. Но на $$$2$$$ и на $$$5$$$ число из одних единиц никогда не поделится, на $$$3$$$ поделится, только в том случае, если сумма его цифр, то есть когда $$$n$$$ кратно $$$3$$$. Несложно понять что число $$$z$$$ делится на $$$7$$$ тогда и только тогда, когда $$$n$$$ кратно $$$6$$$, это также можно можно доказать по индукции. Но это значит, что в этом случае $$$z$$$ также делилось на $$$3$$$, а значит его можно было не разбирать отдельно.

Итоговая сложность: $$$O(\sqrt{n})$$$

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tests;
    cin >> tests;
    while (tests--) {
        string s;
        cin >> s;
        int n = int(s.size());
        if (s == "111") {
            cout << "YES\n";
            continue;
        }
        if (n == 1 && (((s[0] - '0') >= 4 && (s[0] - '0') % 2 == 0) || s[0] == '9')) {
            cout << "YES\n";
            continue;
        }
        if (n != 1 && s[0] != '1') {
            cout << "YES\n";
            continue;
        }
        bool found = false;
        for (int d = 2; d * d <= n && !found; ++d) {
            if (n % d == 0) {
                cout << "YES\n";
                found = true;
            }
        }
        if (!found)
            cout << "NO\n";
    }
    return 0;
}

Переформулируем задачу:

Дана строка $$$s$$$, $$$n = |s|$$$, а также целое число $$$x$$$. В строке $$$s$$$ мы можем перевернуть любой отрезок от $$$l$$$ до $$$r$$$ $$$(1 \le l \le r \le n)$$$. Пусть длина наибольшей подстроки нашей строки, состоящей только из букв $$$p$$$ равна $$$len_p$$$. Нам нужно максимизировать $$$len_p - k ⋅ x$$$, где $$$k$$$ — количество переворотов.

Рассмотрим две непересекающиеся подстроки, состоящие только из букв $$$p$$$ $$$-$$$ $$$s_{[i;j]}$$$ и $$$s_{[k;l]}$$$. Мы можем склеить их в одну большую подстроку, состоящую только из $$$p$$$, ровно за $$$x$$$. А значит можно воспользоваться жадным алгоритмом. Найдём длины всех подстрок, состоящих только из букв $$$p$$$, и поместим их в массив $$$lens$$$; отсортируем $$$lens$$$ по невозрастанию. Первоначально $$$len_p = lens[0]$$$. Если $$$lens$$$ пуст, то $$$len_p = 0$$$.

Утверждение: Нам всегда выгодно к $$$len_p$$$ прибавлять только $$$lens_i \gt x$$$.

Доказательство: Пусть наш нынешний ответ $$$len_p - k ⋅ x$$$ и наш очередной $$$lens_i \le x$$$, тогда после прибавления $$$lens_i$$$ получаем:

$$$len_p + lens_i - (k + 1) ⋅ x \le len_p - k ⋅ x$$$, а значит эта операция бессмысленна.

Тогда, пока есть $$$lens_i \gt x$$$, то прибавляем его к $$$len_p$$$ и обновляем $$$k$$$.

Итоговая сложность: $$$O(n \log n)$$$

$$$PS:$$$ Ниже будет добавлен код от Golden_Square за $$$O(n)$$$. Оставляем понять идею кода читателю :).

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        int n, x;
        string s;
        cin >> n >> x >> s;
        vector<int> lens;
        int len = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'p') {
                ++len;
            } else if (len) {
                lens.push_back(len);
                len = 0;
            }
        }
        if (len)
            lens.push_back(len);
        if (lens.empty()) {
            cout << 0 << '\n';
            continue;
        }
        sort(lens.rbegin(), lens.rend());
        int len_p = lens[0];
        int k = 0;
        for (int i = 1; i < (int)(lens.size()) && lens[i] > x; ++i, ++k) {
            len_p += lens[i];
        }
        cout << len_p - k * x << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n, x;
    cin >> n >> x;

    string a; cin >> a;
    a += ".";
    int cnt = 0, cur = 0, ans = 0;
    for (int i = 0; i <= n; i++) {
        if (a[i] == 'p') {
            cur++;
        } else {
            ans = max(ans, cur + cnt);

            if (cur > x) {
                cnt += cur - x;
            }
            cur = 0;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t; cin >> t;
    while (t--) {
        solve();
    }
}

Подменим условие: скажем, что когда два муравья сталкиваются друг с другом, то они не разворачиваются, а продолжают ползти в те же стороны, что и раньше. Так как все муравьи ползли с одинаковой скоростью, то после такой подмены условия общая картина задачи, а именно координаты муравьëв и их направления не поменяется, значит так можно сделать. Случай же когда $$$3$$$ и более муравья столкнутся в одной точке невозможен, так как тогда за $$$d$$$ времени до столкновения хотя бы два из этих муравьëв ползли в одной точке, что невозможно, так как стартовали они все в разных точках.

В таком случае задачу можно решить просто посчитав время, за которое каждый отдельный муравей выползет с тарелки, игнорируя всех кроме него и выбрав из этих значений максимум.

Let's change the condition: let's say that when two ants collide with each other, they don't turn around, but continue to crawl in the same directions as before. Since all ants have the same speed then after such a change of condition the general picture of the problem, specifically the positions of the ants, their speeds and directions will not change, so this can be done. The case when $$$3$$$ or more ants collide at one point is impossible, because then for the $$$d$$$ of time before the collision at least $$$2$$$ of these ants were crawling at the same point, which in turn is impossible due to the fact that all ants started at different points.

Then problem can be solved by simply calculating the time it takes each individual ant to reach the spoon, ignoring everyone except it and choosing the maximum of these values.

#include <bits/stdc++.h>

using namespace std;

constexpr double PI = acos(-1.0);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double R;
    cin >> R;
    int n;
    cin >> n;
    double cir = PI * 2, ans = 0;
    for (int i = 0; i < n; ++i) {
        double a;
        string d;
        cin >> a >> d;
        ans = max(ans, (d == "cw" ? a : (cir - a)) * R);
    }
    cout << fixed << setprecision(9) << ans << '\n';
    return 0;
}

При разработке этой задачи я столкнулся с проблемой в виде ввода $$$10^6$$$ чисел с плавающей точкой. После некоторых манипуляций стало понятно, что если вводить в C++ тип $$$long$$$ $$$double$$$ в этой задаче, то решение упадёт с вердиктом $$$TLE$$$.

Также, если вводить $$$double$$$ без ускорителей ввода-вывода, то решение также упадёт с вердиктом $$$TLE$$$.

Поэтому, в этой задаче правильным подходом было использование типа $$$double$$$ и ускорителей ввода-вывода. Также, можно было использовать функции $$$scanf$$$ и $$$printf$$$. Они ускоряли код в $$$2$$$ раза, относительно варианта с обычном $$$cin$$$ и $$$cout$$$.

$$$PS$$$: Решение на $$$Pypy$$$ спокойно залетало в заданное ограничение времени.

Пусть $$$W$$$ — суммарная стоимость всех предметов. Применим идею рюкзака с неограниченным количеством предметов, которые мы можем взять. Заведем массив $$$d(i,c)$$$ — максимальная стоимость любого количества вещей типов от 1 до $$$i$$$, суммарным весом до $$$c$$$ включительно. Изначально заполним его нулями.

Меняя $$$i$$$ от 1 до $$$n$$$, рассчитаем на каждом шаге $$$d(i,c)$$$ для $$$c$$$ от $$$0$$$ до $$$W$$$.
$$$d(i,c) = d(i-1,c)$$$, для $$$c \le a_i - 1$$$.

$$$d(i,c) = max(d(i−1,c),d(i,c−w_i)+p_i)$$$, для всех остальных $$$c$$$.

Далее для каждого $$$i$$$ от 1 до $$$n$$$ выводим значение $$$d(i, k \cdot i)$$$;

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rep(x) for (int rep_i = 0; rep_i < x; rep_i++)
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using db = double;
const int maxn = 200100;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0);
minstd_rand rng(time(0));

int dp[1010][100010];

signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(8);

    int n, coin;
    cin >> n >> coin;
    vector<int> w(n + 1, 0), c(n + 1, 0);

    rep(n)cin >> w[rep_i + 1];
    rep(n)cin >> c[rep_i + 1];

    for (int i = 1; i <= n; i++) {
        for (int k = 0; k <= w[i] - 1; k++) {
            dp[i][k] = dp[i - 1][k];
        }
        for (int k = w[i]; k <= 100010; k++) {
            dp[i][k] = max(dp[i - 1][k], dp[i][k - w[i]] + c[i]);
        }

        cout << dp[i][coin*i] << endl;
    }
    return 0;
}

Получим координаты центра для точек $$$A$$$ и $$$B$$$ с координатами $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ соответственно. Для остальных делается аналогично. Пусть точка $$$C_1$$$ — третья вершина равностороннего треугольника, построенного на $$$AB$$$.

Точка $$$M$$$ с координатами $$$(\frac{x_1+x_2}{2}, \frac{y_1+y_2}{2})$$$ — середина отрезка $$$AB$$$. Вектор $$$v$$$ перпендикулярный к $$$AB$$$ и равный по длине высоте $$$C_1M$$$(очевидно основание высоты в равностороннем треугольнике — $$$M$$$) — $$$((y_2 - y_1) \cdot \frac{\sqrt{3}}{2}, (x_1 - x_2) \cdot \frac{\sqrt{3}}{2})$$$.

Тогда, если отложить от $$$M$$$ вектор равный $$$\frac{v}{3}$$$, то мы получим нужную нам точку $$$O$$$. (Так как если отложить просто $$$v$$$, то мы получим точку $$$C$$$, а $$$\frac{C_1O}{OM} = 2$$$)

$$$O = (\frac{x_1+x_2}{2} + (y_2 - y_1) \cdot \frac{\sqrt{3}}{6}, \frac{y_1+y_2}{2} + (x_1 - x_2) \cdot \frac{\sqrt{3}}{6})$$$.

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rep(x) for (int rep_i = 0; rep_i < x; rep_i++)
#define endl '\n'
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using db = double;
const int maxn = 200100;
const int MOD = 1e9 + 7;
const db PI = acos(-1.0);

db sq(db x) {
    return x * x;
}

struct point {
    db x, y;

    point() {}

    point(db x_, db y_) {
        x = x_;
        y = y_;
    }

    point(point p1, point p2) {
        x = p2.x - p1.x;
        y = p2.y - p1.y;
    }

    db dist(point p) {
        return sqrt(sq(x - p.x) + sq(y - p.y));
    }

};

point solve(point x1, point x2) {
    point m = point((x1.x + x2.x) / 2, (x1.y + x2.y) / 2);
    db d = x1.dist(x2);
    point x3 = point(m.x + (x2.y - x1.y) * sqrt(3) / 6, m.y + (x1.x - x2.x) * sqrt(3) / 6);

    return x3;
}



signed main() {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(6);

    db x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    point p1(x1, y1), p2(x2, y2), p3(x3, y3);

    point ans1 = solve(p2, p1);
    cout << ans1.x << ' ' << ans1.y << endl;
    point ans2 = solve(p3, p2);
    cout << ans2.x << ' ' << ans2.y << endl;
    point ans3 = solve(p1, p3);
    cout << ans3.x << ' ' << ans3.y << endl;
    rep(3)
        cout << ans1.dist(ans2) << endl;
    return 0;
}

Задача была на применение идеи динамического программирования. В данной задачи мы используем динамическое программирование по цифрам.

Ключевая идея задачи: пусть $$$f(x)$$$ — количество нужных нам чисел на отрезке $$$[0,x]$$$. Тогда количество нужных чисел на отрезке $$$[l, r]$$$ вычисляется как $$$f(r) - f(l - 1)$$$.

Заведём динамику $$$dp_{i,prod,cnt,pref,zero}$$$, где мы уже расставили $$$i$$$ цифр, их произведение это $$$prod$$$, а количество простых цифр $$$cnt$$$. Также, есть два параметра — $$$pref$$$ и $$$zero$$$. $$$pref$$$ показывает совпадаем ли мы с префиксом числа. $$$zero$$$ показывает ставили ли мы до этого момента только цифру $$$0$$$.

Чтобы пересчитать нашу динамику нужно понять, какие цифры мы можем поставить на очередном шаге. Если $$$pref = true$$$, то мы можем поставить цифру, которая не превышает $$$s_i$$$. Иначе, мы можем поставить любую цифру. Пусть эта цифра будет хранится в переменной $$$max_{digit}$$$.

Пересчёт будет таким: $$$dp_{i,prod,cnt,pref,zero} = \sum_{digit=0}^{max_{digit}} dp_{i + 1,mod(prod⋅digit, k),mod(cnt+prime(digit),2),npref,nzero}$$$

Где, $$$mod(x, m) = x$$$ % $$$m$$$, $$$prime(x)$$$ — проверяет, что $$$x$$$ — простое число, $$$npref = pref$$$ && $$$digit == max_{digit}$$$, $$$nzero = zero$$$ && $$$digit == 0$$$.

База динамики: $$$dp_{|s|,0,cnt,pref,0} = cnt ==$$$ ($$$f == 2$$$ ? $$$cnt$$$ : $$$f$$$).

Конечно, все ячейки $$$dp$$$ надо держать по модулю $$$10^8+73$$$, а также надо учесть отдельно случай с числом $$$l$$$, ибо мы не можем наивно вычесть $$$1$$$ из числа $$$l$$$.

Итоговая сложность: $$$O(|r|⋅k⋅8)$$$

Обратитесь к реализации, чтобы было более понятнее!

#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = int(1e8) + 73;

string l, r;
int k, f;
int dp[1001][1001][2][2][2];

bool prime(int x) {
    return x == 2 || x == 3 || x == 5 || x == 7;
}

int mod(int x, int m) {
    return x % m;
}

int rec(const string& s, int i, int prod, int cnt, int pref, int zero) {
    if (i == int(s.size()))
        return !zero && !prod && cnt == (f == 2 ? cnt : f);
    int &res = dp[i][prod][cnt][pref][zero];
    if (res != -1)
        return res;
    res = 0;
    int max_digit = pref ? s[i] - '0' : 9;
    for (int digit = 0; digit <= max_digit; ++digit) {
        int nprod = mod((zero && digit ? 1 : prod) * digit, k); // (если zero == 1 и digit != 0, то prod = 1, иначе просто равен prod
        int ncnt = mod(cnt + prime(digit), 2);
        int npref = pref && digit == max_digit;
        int nzero = zero && digit == 0;
        res += rec(s, i + 1, nprod, ncnt, npref, nzero);
        res = mod(res, MOD);
    }
    return res;
}

int get_count(const string& number) {
    auto start = &dp[0][0][0][0][0];
    fill(start, start + sizeof(dp) / 4, -1);
    return rec(number, 0, 0, 0, 1, 1);
}

int main() {
    cin >> l >> r >> k >> f;
    int ans = get_count(r) - get_count(l);
    if (ans < 0) ans += MOD;
    int prod = 1, cnt = 0;
    for (int i = 0; i < int(l.size()); ++i) {
        int digit = l[i] - '0';
        prod *= digit;
        prod = mod(prod, k);
        cnt += prime(digit);
        cnt = mod(cnt, 2);
    }
    ans += !prod && cnt == (f == 2 ? cnt : f);
    ans = mod(ans, MOD);
    cout << ans << '\n';
    return 0;
}

Заметим, что если у $$$k$$$ есть какой-нибудь простой делитель $$$d \gt 7$$$, то в числе должен быть обязательно $$$0$$$. Ибо, мы не можем получить какое-нибудь простое число большее, чем $$$7$$$. Количество таких чисел можно посчитать при помощи обычного динамического программирования по цифрам.

Иначе, давайте создадим массив $$$dp$$$ со следующими параметрами: $$$dp_{i,flag,a,b,c,d,cnt}$$$, где $$$i$$$ — количество рассмотренных разрядов, $$$flag$$$ — превысили ли мы число, $$$a, b, c, d$$$ — степени вхождения $$$2, 3, 5, 7$$$ соответственно, $$$cnt$$$ — количество простых цифр по модулю $$$2$$$.

Утверждается, что при заданных ограничениях на $$$k$$$ у него будет не более $$$32$$$ делителя. Тогда, можно делать вот такой пересчёт динамики:

Смотрим, сколько в цифру входит простых множителей и обновляем $$$dp$$$. Например, если мы ставим цифру $$$6$$$ пересчёт будет такой:

$$$dp_{i,flag1,a,b,c,d,cnt}$$$ += $$$dp_{i-1,flag,a-1,b-1,c,d,cnt}$$$.

Ответ будет находится в $$$dp_{|s|,flag,A,B,C,D,cnt}$$$, где $$$A, B, C, D$$$ — степени вхожения $$$2, 3, 5, 7$$$ в $$$k$$$ соответственно, а $$$flag$$$ и $$$cnt$$$ — которые нам нужны.

Для оптимизации динамики по памяти можно хранить только $$$2$$$ последних слоя.

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod = 1e8 + 73;
vector<int> w;
int a, b, c, d;
vector<vector<int>> v;
inline int min(int a, int b) {
    if(a < b) {
        return a;
    }
    return b;
}
int f;
int solve1(string s) {
    if(s[0] == '0') {
        return 0;
    }
    int n = s.size();
    vector<vector<vector<vector<vector<vector<vector<int>>>>>>> dp(2, vector<vector<vector<vector<vector<vector<int>>>>>>(2, vector<vector<vector<vector<vector<int>>>>>(a+1, vector<vector<vector<vector<int>>>>(b+1, vector<vector<vector<int>>>(c+1, vector<vector<int>>(d+1, vector<int>(2, 0)))))));
    int y = 0;
    int a0 = 0, b0 = 0, c0 = 0, d0 = 0;
    for(int ii = 1; ii <= n; ++ii) {
        int x = s[ii-1]  - '0';
        y ^= w[x];
        if(x == 0) {
            a0 = a;
            b0 = b;
            c0 = c;
            d0 = d;
            dp[1][0][a][b][c][d][y] = 1;
        }else {
            int aa, bb, cc, dd;
            aa = v[x][0];
            bb = v[x][1];
            cc = v[x][2];
            dd = v[x][3];
            a0 += aa;
            b0 += bb;
            c0 += cc;
            d0 += dd;
            dp[1][0][min(a0, a)][min(b0, b)][min(c0, c)][min(d0, d)][y] = 1;
        }
        for(int i = 1; i < x; ++i) {
            int aaa = v[i][0];
            int bbb = v[i][1];
            int ccc = v[i][2];
            int ddd = v[i][3];
            for(int j = 0; j <= 1; ++j) {
                for(int aa = 0; aa <= a; ++aa) {
                    for(int bb =0 ; bb <= b; ++bb) {
                        for(int cc =0 ; cc <= c; ++cc) {
                            for(int dd =0 ; dd <= d; ++dd) {
                                dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j] += dp[0][0][aa][bb][cc][dd][j ^ w[i]];
                                if(dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j] >= mod) {
                                    dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j]-=mod;
                                }
                                dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j] += dp[0][1][aa][bb][cc][dd][j ^ w[i]];
                                if(dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j] >= mod) {
                                    dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j]-=mod;
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int i = max(1ll, x); i <= 9; ++i) {
            int aaa = v[i][0];
            int bbb = v[i][1];
            int ccc = v[i][2];
            int ddd = v[i][3];
            for(int j = 0; j <= 1; ++j) {
                for(int aa = 0; aa <= a; ++aa) {
                    for(int bb =0 ; bb <= b; ++bb) {
                        for(int cc =0 ; cc <= c; ++cc) {
                            for(int dd =0 ; dd <= d; ++dd) {
                                dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j ^ w[i]] += dp[0][1][aa][bb][cc][dd][j];
                                if(dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j ^ w[i]] >= mod) {
                                    dp[1][1][min(a, aa+aaa)][min(b, bb+bbb)][min(c, cc+ccc)][min(d, dd+ddd)][j ^ w[i]]-=mod;
                                }
                            }
                        }
                    }
                }
            }
        }
        for(int j = 0; j <= 1; ++j) {
            for(int aa = 0; aa <= a; ++aa) {
                for(int bb =0 ; bb <= b; ++bb) {
                    for(int cc =0 ; cc <= c; ++cc) {
                        for(int dd =0 ; dd <= d; ++dd) {
                            dp[1][1][a][b][c][d][j] += dp[0][1][aa][bb][cc][dd][j];
                            if(dp[1][1][a][b][c][d][j] >= mod) {
                                dp[1][1][a][b][c][d][j] -= mod;
                            }
                            if(x) {
                                dp[1][1][a][b][c][d][j] += dp[0][0][aa][bb][cc][dd][j];
                            }
                            if(dp[1][1][a][b][c][d][j] >= mod) {
                                dp[1][1][a][b][c][d][j] -= mod;
                            }
                        }
                    }
                }
            }
        }

        if(ii == 1) {
            for(int j = 1; j < x; ++j) {
                dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] += 1;
                if(dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] >= mod) {
                    dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] -= mod;
                }
            }
        }else {
            for(int j = 1; j <= 9; ++j) {
                dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] += 1;
                if(dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] >= mod) {
                    dp[1][1][min(v[j][0], a)][min(v[j][1], b)][min(v[j][2], c)][min(v[j][3], d)][w[j]] -= mod;
                }
            }
        }
        swap(dp[0], dp[1]);
        for(int i = 0; i <= 1; ++i) {
            for(int aa = 0; aa <= a; ++aa) {
                for(int bb =0 ; bb <= b; ++bb) {
                    for(int cc =0 ; cc <= c; ++cc) {
                        for(int dd =0 ; dd <= d; ++dd) {
                            for(int z =0; z <= 1; ++z) {
                                dp[1][i][aa][bb][cc][dd][z] = 0;
                            }
                        }
                    }
                }
            }
        }
    }

    if(f == 0) {
        return dp[0][0][a][b][c][d][0] + dp[0][1][a][b][c][d][0];
    }
    if(f == 1) {
        return dp[0][0][a][b][c][d][1] + dp[0][1][a][b][c][d][1];
    }
    if(f == 2) {
        return dp[0][0][a][b][c][d][1] + dp[0][1][a][b][c][d][1] + dp[0][0][a][b][c][d][0] + dp[0][1][a][b][c][d][0];
    }
}

int solve2(string s) {
    if(s[0] == '0') {
        return 0;
    }
    int n = s.size();
    vector<vector<vector<vector<int>>>> dp(2, vector<vector<vector<int>>> (2, vector<vector<int>> (2, vector<int> (2))));
    int y = 0;
    int z = 0;
    for(int ii = 1; ii <= n; ++ii) {
        int x = s[ii-1] - '0';
        y ^= w[x];
        if(x == 0) {
            z = 1;
        }
        dp[1][0][y][z] = 1;

        for(int i = 1; i < x; ++i) {
            for(int j = 0; j <= 1; ++j) {
                for(int u =0 ; u <= 1; ++u) {
                    dp[1][1][j][u] += dp[0][1][j^w[i]][u];
                    if(dp[1][1][j][u] >= mod) {
                        dp[1][1][j][u] -= mod;
                    }
                    dp[1][1][j][u] += dp[0][0][j^w[i]][u];
                    if(dp[1][1][j][u] >= mod) {
                        dp[1][1][j][u] -= mod;
                    }
                }
            }
        }
        for(int i = max(x, 1ll); i <= 9; ++i) {
            for(int j = 0; j <= 1; ++j) {
                for(int u =0 ; u <= 1; ++u) {
                    dp[1][1][j][u] += dp[0][1][j^w[i]][u];
                    if(dp[1][1][j][u] >= mod) {
                        dp[1][1][j][u] -= mod;
                    }
                }
            }
        }
        if(ii > 1) {
            for(int j = 0; j <= 1; ++j) {
                for(int u =0 ; u <= 1; ++u) {
                    dp[1][1][j][1] += dp[0][1][j][u];
                    if(dp[1][1][j][1] >= mod) {
                        dp[1][1][j][1] -= mod;
                    }
                    if(x) dp[1][1][j][1] += dp[0][0][j][u];
                    if(dp[1][1][j][1] >= mod) {
                        dp[1][1][j][1] -= mod;
                    }
                }
            }
        }

        if(ii ==  1) {
            for(int i = 1; i < x; ++i) {
                dp[1][1][w[i]][0] += 1;
                if(dp[1][1][w[i]][0] >= mod) {
                    dp[1][1][w[i]][0] -= mod;
                }
            }
        }else {
            for(int i = 1; i <= 9; ++i) {
                dp[1][1][w[i]][0] += 1;
                if(dp[1][1][w[i]][0] >= mod) {
                    dp[1][1][w[i]][0] -= mod;
                }
            }
        }
        swap(dp[0], dp[1]);
        for(int i = 0; i <2; ++i) {
            for(int z =0 ; z < 2; ++z) {
                for(int t =0; t < 2; ++t) {
                    dp[1][i][z][t] = 0;
                }
            }
        }
    }
    if(f == 0) {
        return dp[0][0][0][1] + dp[0][1][0][1];
    }
    if(f == 1) {
        return dp[0][0][1][1] + dp[0][1][1][1];
    }
    if(f == 2) {
        return dp[0][0][0][1] + dp[0][1][0][1] + dp[0][0][1][1] + dp[0][1][1][1];
    }
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string l, r;
    cin >> l >> r;
    int k;
    cin >> k >> f;
    v.assign(10, {});
    w.assign(10, 0);
    w[2] = w[3] = w[5] = w[7] = 1;
    v[1] = {0, 0, 0, 0};
    v[2] = {1, 0, 0, 0};
    v[3] = {0, 1, 0, 0};
    v[4] = {2, 0, 0, 0};
    v[5] = {0, 0, 1, 0};
    v[6] = {1, 1, 0, 0};
    v[7] = {0, 0, 0, 1};
    v[8] = {3, 0, 0, 0};
    v[9] = {0, 2, 0, 0};
    while(k % 2 == 0) {
        a++;
        k /= 2;
    }
    while(k % 3 == 0) {
        b++;
        k /= 3;
    }
    while(k % 5 == 0) {
        c++;
        k /= 5;
    }
    while(k % 7 == 0) {
        d++;
        k /= 7;
    }
    if(k > 1) {
        int ans = solve2(r);
        if(l.back() > '0') {
            l.back()--;
        }else {
            int cnt = 0;
            for(auto x : l) {
                x = x - '0';
                cnt ^= w[x];
            }
            if(f == 0 && cnt == 0) {
                ans++;
            }
            if(f == 1 && cnt == 1) {
                ans++;
            }
            if(f == 2) {
                ans++;
            }
        }
        ans -= solve2(l);
        ans %= mod;
        ans += mod;
        ans %= mod;
        cout << ans;
    }else {
        int ans = solve1(r);
        if(l.back() > '0') {
            l.back()--;
        }else {
            int cnt = 0;
            for(auto x : l) {
                x = x - '0';
                cnt ^= w[x];
            }
            if(f == 0 && cnt == 0) {
                ans++;
            }
            if(f == 1 && cnt == 1) {
                ans++;
            }
            if(f == 2) {
                ans++;
            }
        }
        ans -= solve1(l);
        ans %= mod;
        ans += mod;
        ans %= mod;
        cout << ans;
    }
    return 0;
}