0

Никак не могу справиться с задачей, заданной в ВУЗе - пишет, что превышен лимит времени. Я вообще не понимаю как тут её решить. Вот сама задача:

введите сюда описание изображения А вот мой код:

#include <iostream>
#include <cmath>
using namespace std;
int f(int n)
{
   int i, c=0;
   for (i=1; i<=sqrt(n); i++)
   {
      if (n%i==0) c++;
   }
   if (sqrt(n)==int(sqrt(n))) 
      return 2*c-1;
   return 2*c; 
}

int main()
{
   int i,m,n,s=0;
   cin>>n>>m;
   for (i=2;i<=n;i++)
   {
      if (f(i)==m)
         s++;
   }
   cout<<s<<endl;
}

4 ответа 4

1

Ох, побьют меня сейчас за неспортивное поведение... :( Но задачка интересная, хотелось бы узнать - все же нет ли какого-то способа побыстрее, чем перебор...

У меня - просто разложение на простые множители и произведение увеличенных на 1 степеней.

#include <iostream>

using namespace std;

const unsigned int primes[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
    61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
    131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 
    197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 
    271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
    353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 
    433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 
    509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 
    601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 
    677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 
    769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 
    953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 
    1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 
    1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 
    1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 
    1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 
    1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 
    1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 
    1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 
    1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 
    1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 
    1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 
    1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 
    1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 
    2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 
    2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 
    2203, 2207, 2213, 2221, 2237};

unsigned CountOf(unsigned n, unsigned M)
{
    unsigned count = 1;
    if (n > 1)
    {
        for(unsigned q = 0, t = primes[0];
            t*t <= n && q < sizeof(primes)/sizeof(primes[0]);
            t = primes[++q])
        {
            if (n % t == 0)
            {
                unsigned d;
                for (d=0; !(n%t); ++d) n/=t;
                count *= d+1;
                if (count > M) return 0;
            }
        }
        if (n > 1) count *= 2;
        return count == M;
    }
    else return 0;
}


int main()
{
    unsigned N, M, count = 0;
    cin >> N >> M;

    for(unsigned i = 2; i <= N; ++i)
        count += CountOf(i,M);

    cout << count << endl;
}

Update
Немного ускорил - не считаем все корни, если уже перевалили нужное число.

1
  • Ооо, спасибо огромной, сайт принял программу, сейчас мне осталось разобраться в коде и до конца понять что тут да как. Спасибо)
    – zzronn
    11 мар 2018 в 10:44
1

Давайте научимся за линейное время находить все простые числа, заодно составим табличку для факторизации числа за кол-во чисел в факторизации, таким образом мы получим решение за O(N * const)

#include <iostream>
#include <vector>
using namespace std;
int n, m;
const int N = 5e6 + 3;
int lp[N + 1];
vector<int> pr;
void gen_primes() {
    for (int i = 2; i <= N; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j < (int)pr.size() && pr[j] <= lp[i] && i * pr[j] <= N; ++j)
            lp[i * pr[j]] = pr[j];
    }
}
int count(int a) {
    int ans = 1, last_prime = lp[a], cur = 0;
    while (a > 1) {
        if (lp[a] != last_prime) {
            ans *= (cur + 1);
            cur = 0;
            last_prime = lp[a];
        }
        cur++;
        a /= lp[a];
        if (lp[a] == 1) break;
    }
    return ans * (cur + 1);
}

int32_t main() {
    pr.reserve(350000);
    gen_primes();
    cin >> n >> m;
    int ans = 0;
    for (int i = 2; i <= n; i++)
        ans += (count(i) == m);
    cout << ans;
}

Спойлер - зашло

5
  • Ускоряю генерацию простых чисел в два раза, а поиск множителей логарифмически. Бесплатно, без регистрации и смс. ПС. Код с комментариями намного полезнее, чем без. 9 дек 2019 в 18:55
  • Предложенный вами алгоритм работает явно дольше, чем предложенный мной. 9 дек 2019 в 18:58
  • Я ещё ничего не предлагал 🤔 9 дек 2019 в 18:59
  • Отличное решение! 31 дек 2021 в 8:17
  • Функция count, кажется, имеет сложность хуже чем O(n). Там что-то вроде O(nlog*(n))? 31 дек 2021 в 8:30
0
bool f(int n, int m) {
   bool res = false;
   int c = 0;
   for (int i = 2; i <= sqrt(n); i++) {
       if (n % i == 0) 
           c++;
       if (c == m) {
           break;
           res = true;           
       }
   }
}

И это в main

int main()
{
   int m, n, s = 0;
   cin >> n >> m;
   for (int i = 2; i <= n; i++)
   {
      if (f(i))
         s++;
   }
   cout << s << endl;
}

UPD: Я бы посоветовал вам не объявлять переменные для цикла for вне самого цикла, если уж не используете значение i после его завершения. А так же делайте отступы между арифм. операциями и всем остальным

2
  • Хм..., нужно сосчитать количество чисел от 1 до n включительно у которых количество делителей равно m. Как я понял, у вас в функции если количество делителей у числа больше чем m то он выводит false и всё. Но если количество делителей у числа != m то он должен тоже вывести false, даже проверяя работу программы числами из примера он уже выводит неправильно. А за совет про i вне цикла и отступы спасибо, буду использовать.
    – zzronn
    11 мар 2018 в 10:31
  • Уже исправил. На счёт i, все переменные которые работают только в цикле, лучше и объявлять внутри цикла, это упрощает отладку программы, да и удобство. А с отступами это чисто для читабельности. Хороший код принято писать не "слипшимся"
    – BogdanBida
    11 мар 2018 в 10:36
0

Решение с линейным решетом и почти линейным разложением трудно превзойти по скорости. Зато эту задачу можно решить значительно проще. Решение укладывается в ограничения по памяти и скорости с запасом, не содержит корней и даже деления!

Идея: заведём вектор с количеством делителей данного числа. Перебираем делители от единицы до n. Для делителя i увеличиваем счётчик в ячейках i, 2i, 3i, ... Считаем количество m-простых:

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> n_divs(n + 1, 0);

    int n_mprimes = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            ++n_divs[j];
        }
        if (n_divs[i] == m) {
            ++n_mprimes;
        }
    }
    std::cout << n_mprimes << '\n';
}
$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 martian-primes.cpp 

$ time echo 5000000 12 | ./a.out 
429792

real  0m0.476s
user  0m0.468s
sys   0m0.004s

Это в два раза медленее чем лучшее решение, зато в десять раз проще.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.