Делители

@dmitrii2000 · Регистрация: 03.05.2020

Студворк — интернет-сервис помощи студентам

Дано натуральное число n. Подсчитайте количество таких пар чисел (a;b), что:

a и b — делители n;
a<b;
a и b — взаимно простые;
ab≤n.
Входные данные

Вводится натуральное число n≤108.

Выходные данные

Выведите количество таких пар.

Примеры
Ввод
10
Вывод
4

Verevkin · 09.07.2021, 09:04

Сообщение от dmitrii2000

Примеры
Ввод
10
Вывод
4

10 = 1 * 10 = 2 * 5
А остальные 2 пары?
-------
А, поняль:

Код

# 10 ≥ 1 * 2
# 10 ≥ 1 * 5
# 10 ≥ 1 * 10
# 10 ≥ 2 * 5

$ Всего пар: 4

Добавлено через 22 минуты

C++

#include <cstdio>
 
unsigned gcd(unsigned a, unsigned b)
{
  if (!a || !b) return a + b;
  while (a != b) if (a > b) a -= b; else b -= a;
  return a; 
}
 
unsigned pairs_count(unsigned n)
{
  unsigned total = 0;
  for (unsigned a = 1; a * a <= n; a++)
    for (unsigned b = a + 1; a * b <= n; b++)
      if (!(n % a) && !(n % b) && gcd(a, b) == 1) 
        total++, printf("# %u ≥ %u * %u\n", n, a, b);
  return total;  
}
 
int main()
{
  unsigned n = 0;
  do printf("\n? n = ");
  while (scanf("%u", &n) != 1 || !n);
  printf("$ Всего пар: %u\n", pairs_count(n));
  return 0;
}

@dmitrii2000 · 09.07.2021, 09:23 **[ТС]**

Программа не проходит по времени.

Verevkin · 09.07.2021, 09:27

Сообщение от dmitrii2000

Программа не проходит по времени.

В условии задачи про время ничего не сказано.
И как и кем это время замеряется и с какого момента?

@Super-Hacker · 09.07.2021, 10:24

https://en.cppreference.com/w/cpp/numeric/gcd
Потому что mod использовать надо))

C++

unsigned gcd(unsigned a, unsigned b)
{
  if (!a || !b) return a + b;
  while ((a + b) != 0) if (a > b) a %= b; else b %= a;
  return a; 
}

Добавлено через 8 минут
Ладно. Постыдно получилось

C++

unsigned gcd (unsigned a, unsigned b) 
{
    while (b != 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

Добавлено через 21 секунду
Но кто знает, в чём на самом деле дело

Verevkin · 09.07.2021, 10:28

Сообщение от Super-Hacker

Потому что mod использовать надо))

нетЪ.

Сообщение от Super-Hacker

Но кто знает, в чём на самом деле дело

чел копипастит исходник, не глядя, на сцайт, где бот его компилит, запускает и пытается взаимодействовать. Думаю, ручной ввод данных там не предусмотрен и происходит через файл.

Байт · 09.07.2021, 10:38

Небольшая модификация

C++

unsigned pairs_count(unsigned n)
{
  unsigned total = 0;
  for (unsigned a = 1; a * a <= n; a++)
    if (n%a) continue;
    for (unsigned b = a + 1;  b <= n/a; b++)
      if (!(n % b) && gcd(a, b) == 1) 
        total++, printf("# %u ≥ %u * %u\n", n, a, b);
  return total;  
 
}

Verevkin · 09.07.2021, 10:46

Сообщение от Байт

Небольшая модификация

А смысол? По умолчанию логические выражения считаются не полностью, а до очевидного результата.

Verevkin · 09.07.2021, 10:53

Провёл эксперимет со временем. Результаты:

C++

#include <cstdio>
#include <cstdlib>
#include <ctime>
 
unsigned gcd(unsigned a, unsigned b)
{
  if (!a || !b) return a + b;
  while (a != b) if (a > b) a -= b; else b -= a;
  return a; 
}
 
unsigned pairs_count(unsigned n, clock_t &duration)
{
  unsigned total = 0;
  duration = clock();
  
  for (unsigned a = 1; a * a <= n; a++)
    for (unsigned b = a + 1; a * b <= n; b++)
      if (!(n % a) && !(n % b) && gcd(a, b) == 1) 
        total++;//, printf("# %u ≥ %u * %u\n", n, a, b);
        
  duration = clock() - duration;       
  return total;  
}
 
int main()
{
  system("chcp 65001 && cls");
  unsigned n = 0;
  
  
  do printf("\n? n = ");
  while (scanf("%u", &n) != 1 || !n);
  
  clock_t t;
  printf("$ Всего пар: %u\n", pairs_count(n, t));
  printf("$ Время: %lu мс\n", t);
  return 0;
}

Дальше ускорять смысол есть, как думаете?

Байт · 09.07.2021, 10:54

Сообщение от Verevkin

А смысол?

Меньше проходов внутреннего цикла. Неь заведомо не нужных

Verevkin · 09.07.2021, 10:56

Сообщение от Байт

Меньше проходов внутреннего цикла. Неь заведомо не нужных

Ты операторные скобки забыль.
Но ты прав, скорость увеличилась, конечно.

Байт · 09.07.2021, 11:00

Сообщение от Verevkin

Ты операторные скобки забыль.

Звиняйте....

C++

unsigned pairs_count(unsigned n)
{
  unsigned total = 0;
  for (unsigned a = 1; a * a <= n; a++) {
    if (n%a) continue;
    for (unsigned b = a + 1;  b <= n/a; b++)
      if (!(n % b) && gcd(a, b) == 1) 
        total++, printf("# %u ≥ %u * %u\n", n, a, b);
  }
  return total;  
 
}

Verevkin · 09.07.2021, 11:01

Сообщение от Байт

Звиняйте....

Я вот так допилил:

C++

unsigned pairs_count(unsigned n, clock_t &duration)
{
  unsigned total = 0;
  duration = clock();
  
  for (unsigned a = 1; a * a <= n; a++)
    if (!(n % a)) // модификация (© Байт)
      for (unsigned b = a + 1; a * b <= n; b++)
        if (/*!(n % a) &&*/ !(n % b) && gcd(a, b) == 1) 
          total++;//, printf("# %u ≥ %u * %u\n", n, a, b);
        
  duration = clock() - duration;       
  return total;  
}

@dmitrii2000 · 10.07.2021, 08:37 **[ТС]**

Скиньте решение пожалуйста

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	10.07.2021, 08:37 [ТС]	14
	Скиньте решение пожалуйста 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
		1
	Делители 09.07.2021, 08:08. Показов 1649. Ответов 13 Метки нет (Все метки) Дано натуральное число n. Подсчитайте количество таких пар чисел (a;b), что: a и b — делители n; a<b; a и b — взаимно простые; ab≤n. Входные данные Вводится натуральное число n≤108. Выходные данные Выведите количество таких пар. Примеры Ввод 10 Вывод 4 0

@dmitrii2000 2 / 2 / 0 Регистрация: 03.05.2020 Сообщений: 202
	09.07.2021, 09:23 [ТС]	3
	Программа не проходит по времени. 0

Verevkin Нарушитель 8997 / 4850 / 1119 Регистрация: 12.03.2015 Сообщений: 22,971
	09.07.2021, 09:27	4
	Сообщение от dmitrii2000 Программа не проходит по времени. В условии задачи про время ничего не сказано. И как и кем это время замеряется и с какого момента? 0

Verevkin Нарушитель 8997 / 4850 / 1119 Регистрация: 12.03.2015 Сообщений: 22,971
	09.07.2021, 10:28	6
	Сообщение от Super-Hacker Потому что mod использовать надо)) нетЪ. Сообщение от Super-Hacker Но кто знает, в чём на самом деле дело чел копипастит исходник, не глядя, на сцайт, где бот его компилит, запускает и пытается взаимодействовать. Думаю, ручной ввод данных там не предусмотрен и происходит через файл. 0

Verevkin Нарушитель 8997 / 4850 / 1119 Регистрация: 12.03.2015 Сообщений: 22,971
	09.07.2021, 10:46	8
	Сообщение от Байт Небольшая модификация А смысол? По умолчанию логические выражения считаются не полностью, а до очевидного результата. 0

Байт Диссидент 27697 / 17314 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	09.07.2021, 10:54	10
	Сообщение от Verevkin А смысол? Меньше проходов внутреннего цикла. Неь заведомо не нужных 0

Verevkin Нарушитель 8997 / 4850 / 1119 Регистрация: 12.03.2015 Сообщений: 22,971
	09.07.2021, 10:56	11
	Сообщение от Байт Меньше проходов внутреннего цикла. Неь заведомо не нужных Ты операторные скобки забыль. Но ты прав, скорость увеличилась, конечно. 1