Хорошо, давайте разберём задачу пошагово.

1. Когда число имеет ровно 9 делителей?

Пусть число $n$ имеет простое разложение:

Число делителей тогда равно:

Нам нужно, чтобы $d(n) = 9$.

Разложение числа 9:

• $9 = 9\cdot 1$,
• $9 = 3\cdot 3$.

То есть возможны варианты:

1. $d(n) = 9 \implies a_1 + 1 = 9 \implies a_1 = 8$.
   Тогда $n = p^8$, где $p$ — простое число.

2. $d(n) = 3 \cdot 3 \implies (a_1 + 1)(a_2 + 1) = 3\cdot 3 \implies a_1 = a_2 = 2$.
   Тогда $n = p^2 \cdot q^2$, где $p$ и $q$ — разные простые.

2. Значит, "выходные дни" — это числа вида:

• $p^8 \leq n$,
• $p^2 q^2 \leq n$.

3. Как посчитать количество?

Для заданного $n$:

1. Посчитать количество простых $p$, для которых $p^8 \leq n$.

   $$p \leq \sqrt[8]{n}.$$

2. Посчитать количество пар различных простых $(p, q)$, для которых

   $$p^2 q^2 \leq n \quad \iff \quad pq \leq \sqrt{n}.$$

4. Примеры проверки

• Для $n=5$:
  $\sqrt[8]{5} < 2$, нет простых → 0.
  $\sqrt{5} \approx 2.23$, минимальное $pq = 2\cdot 3 = 6 > 2.23$.
  → Ответ: 0 ✅

• Для $n=120$:
  $\sqrt[8]{120} \approx 1.9$, простых нет.
  $\sqrt{120} \approx 10.95$.
  Пары: $2\cdot 3 = 6 \leq 10.95$, $2\cdot 5 = 10 \leq 10.95$.
  Другие уже больше.
  → Ответ: 2 ✅

• Для $n=365$:
  $\sqrt[8]{365} \approx 2.3$, значит учитываем $p=2$. Получаем число $2^8=256 \leq 365$.
  $\sqrt{365} \approx 19.1$.
  Пары простых $\leq 19$:

  • (2,3)=6
  • (2,5)=10
  • (2,7)=14
  • (2,11)=22 ❌
  • (3,5)=15
    Остальные превышают.
    Итого: 4 пары + 1 (от $2^8$) = 5. ✅

5. Итоговое решение

Алгоритм:

1. Найти все простые до $\sqrt[8]{n}$. Считаем количество — это первый компонент.
2. Найти все простые до $\sqrt{n}$. Перебирать по возрастанию, для каждого $p$ считать, сколько $q$ можно взять, чтобы $pq \leq \sqrt{n}$. Суммировать. Это второй компонент.
3. Сложить оба результата.

Хотите, я напишу для вас готовый код на Python, который работает даже при $n \leq 4 \cdot 10^{12}$?

окей! вот «уникальное» и очень быстрое решение на C++, без плавающих точек, с:

• чёткими целочисленными корнями (k-я степень и √n) на __int128,
• odd-only битовым ситом (храним только нечётные),
• двухуказательным подсчётом пар простых $p<q$ с $pq\le\lfloor\sqrt{n}\rfloor$.

работает за $O(\sqrt n / \log \sqrt n)$ по времени и $O(\sqrt n)$ по памяти (при $n\le 4\cdot10^{12}$ это до ~2·10⁶).

cpp
#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;
using u128 = __uint128_t;

// --------- безопасные целочисленные корни ----------
static inline u64 isqrt_u64(u64 x) {
    // floor(sqrt(x)) без double
    u64 lo = 0, hi = (u64)1e10; // т.к. sqrt(4e12) < 2e6 << 1e10; берём большой верхний предел безопасно
    // но сделаем аккуратнее: верхняя граница не меньше реального корня
    // можно ослабить: hi = min<u64>(x, (u64)2e9);
    hi = min<u64>(x, (u64)2000000000ULL);
    while (lo < hi) {
        u64 mid = (lo + hi + 1) >> 1;
        if ((u128)mid * mid <= x) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

static inline bool pow_leq(u64 base, int k, u64 lim) {
    // проверяет base^k <= lim без переполнений
    u128 acc = 1;
    for (int i = 0; i < k; ++i) {
        acc *= base;
        if (acc > lim) return false;
    }
    return true;
}

static inline u64 iroot_k(u64 n, int k) {
    // floor(n^(1/k)) бинарным поиском и pow_leq
    if (k == 1) return n;
    u64 lo = 0, hi = (k == 2 ? isqrt_u64(n) + 1 : min<u64>(n, (u64)1e6+10));
    // небольшой «запас» для hi; для k>=3 корень сильно меньше 1e6 при наших n
    while (lo < hi) {
        u64 mid = (lo + hi + 1) >> 1;
        if (pow_leq(mid, k, n)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

// --------- odd-only битовое sito до MAX -----------
struct OddBitSieve {
    // храним биты для нечётных: число 2*i+1 соответствует биту i
    int n;                    // верхняя граница включительно
    vector<uint64_t> bits;    // 1 = составное, 0 = возможно простое (для нечётных)
    static inline int idx_of(u64 x) { return int((x - 1) >> 1); } // x нечётное >=1

    explicit OddBitSieve(int N): n(N) {
        int m = (N >= 1) ? (idx_of(N) + 1) : 0;
        bits.assign((m + 63) >> 6, 0);
        if (N >= 1) mark(1); // число 1 не простое
        if (N >= 2) {
            // классическое просеивание только для нечётных
            for (u64 p = 3; p * p <= (u64)N; p += 2) {
                if (!test(p)) {
                    // начинаем с p*p и шагаем по 2p (только нечётные кратные)
                    for (u64 x = p * p; x <= (u64)N; x += (p << 1))
                        mark((int)x);
                }
            }
        }
    }

    inline void mark(int x) {
        // x нечётное
        int i = idx_of(x);
        bits[i >> 6] |= (1ULL << (i & 63));
    }

    inline bool test(int x) const {
        // true -> составное (для нечётных), false -> «возможно простое»
        if (x == 2) return false;        // 2 отдельный случай
        if ((x & 1) == 0) return true;   // чётные > 2 — составные
        int i = idx_of(x);
        return (bits[i >> 6] >> (i & 63)) & 1ULL;
    }

    vector<int> primes() const {
        vector<int> ps;
        if (n >= 2) ps.push_back(2);
        for (int x = 3; x <= n; x += 2)
            if (!test(x)) ps.push_back(x);
        return ps;
    }
};

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

    u64 n;
    if (!(cin >> n)) return 0;

    // 1) корни
    u64 S  = isqrt_u64(n);       // floor(sqrt(n))
    u64 R8 = iroot_k(n, 8);      // floor(n^(1/8))

    // 2) простые до S
    OddBitSieve sieve((int)S);
    vector<int> primes = sieve.primes(); // возрастающий список

    // 3) количество p^8 <= n  <=> p <= R8
    u64 cnt_p8 = 0;
    if (R8 >= 2) {
        cnt_p8 = upper_bound(primes.begin(), primes.end(), (int)R8) - primes.begin();
    }

    // 4) количество пар различных простых p<q: p*q <= S
    // двухуказательный приём
    u64 cnt_pairs = 0;
    int m = (int)primes.size();
    int j = m - 1;
    for (int i = 0; i < m; ++i) {
        while (j > i && (u128)primes[i] * (u128)primes[j] > S) --j;
        if (j <= i) break;
        cnt_pairs += (u64)(j - i);
    }

    cout << (cnt_p8 + cnt_pairs) << '\n';
    return 0;
}

почему это решение надёжно и быстро

• без ошибок округления: все корни считаются целочисленно, проверка степеней идёт через __int128;
• память и скорость: просеиваем только до $\lfloor\sqrt{n}\rfloor\le 2\,000\,000$, причём только нечётные — экономим ×2 память и время;
• подсчёт пар $p<q$ — за один проход двумя указателями $O(\pi(S))$;
• форма с ровно 9 делителями — это только $p^8$ или $p^2q^2$ с разными простыми, что мы и учитываем.

cpp
#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;
using u128 = __uint128_t;

bool pow_leq(u64 a,int k,u64 lim){ u128 x=1; for(int i=0;i<k;i++){ x*=a; if(x>lim) return false; } return true; }
u64 iroot(u64 n,int k){
    if(k==1) return n;
    u64 x = (u64)powl((long double)n, 1.0L/k);
    while(!pow_leq(x,k,n)) --x;
    while(pow_leq(x+1,k,n)) ++x;
    return x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    u64 n; if(!(cin>>n)) return 0;
    u64 S = (u64)sqrtl((long double)n);
    while((u128)(S+1)*(S+1)<=n) ++S;
    while((u128)S*S>n) --S;
    u64 R8 = iroot(n,8);

    vector<char> is(S+1,true);
    is[0]=is[1]=false;
    for(u64 p=2;p*p<=S;++p) if(is[p]) for(u64 x=p*p;x<=S;x+=p) is[x]=false;
    vector<int> pr; pr.reserve(S/log(max<u64>(2,S)));
    for(u64 i=2;i<=S;++i) if(is[i]) pr.push_back((int)i);

    u64 cnt_p8 = upper_bound(pr.begin(), pr.end(), (int)R8) - pr.begin();

    u64 ans = cnt_p8, j = pr.size();
    for(size_t i=0;i<pr.size();++i){
        while(j>i+1 && (u128)pr[i]*pr[j-1]>S) --j;
        if(j<=i+1) break;
        ans += (j-1 - (i+1) + 1);
    }
    cout<<ans<<"\n";
    return 0;
}

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long n; 
    if (!(cin >> n)) return 0;

    unsigned long long S = sqrtl((long double)n);
    while ((S+1)*(S+1) <= n) ++S;
    while (S*S > n) --S;
    unsigned long long R8 = powl((long double)n, 1.0L/8);
    while (powl((long double)R8+1, 8) <= (long double)n) ++R8;
    while (powl((long double)R8,   8) >  (long double)n) --R8;

    vector<char> is(S+1, true);
    is[0]=is[1]=false;
    for (unsigned long long p=2; p*p<=S; ++p) if (is[p])
        for (unsigned long long x=p*p; x<=S; x+=p) is[x]=false;

    vector<int> pr;
    for (unsigned long long i=2; i<=S; ++i) if (is[i]) pr.push_back((int)i);

    unsigned long long ans = upper_bound(pr.begin(), pr.end(), (int)R8) - pr.begin();

    int m = (int)pr.size(), j = m-1;
    for (int i=0; i<m; ++i) {
        while (j>i && (unsigned long long)pr[i]*pr[j] > S) --j;
        if (j<=i) break;
        ans += (unsigned long long)(j - i);
    }

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

cpp
#include <bits/stdc++.h>
using namespace std;

static inline bool ok(unsigned long long A, unsigned long long S){
    if (S < (A<<1)) return false;
    unsigned long long R = S - (A<<1);
    return (R & A) == 0;
}

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

    int t; 
    if(!(cin >> t)) return 0;
    string out;
    out.reserve(t*4);

    for(; t--; ){
        unsigned long long a, s; 
        cin >> a >> s;
        out += ok(a, s) ? "Yes\n" : "No\n";
    }
    cout << out;
    return 0;
}

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; long long s; 
    if (!(cin >> n >> s)) return 0;
    vector<pair<long long,long long>> v(n);
    for (auto &p : v) cin >> p.first >> p.second;      // (c, a)
    sort(v.begin(), v.end());                           // по цене
    long long ans = 0;
    for (auto [c,a] : v) {
        long long t = min(a, s);
        ans += t * c;
        s -= t;
        if (!s) break;
    }
    cout << ans << '\n';
    return 0;
}