#c #math
Вопрос:
Вычислять
n Если есть только один тест, мой код в порядке, но если есть 100000 (1e5) тестов, что я должен сделать, чтобы улучшить свой код?
Например:
Ввод:
60
604 84 940 659 989 497 400 656 805 169 305 141 718 691 500 723 658 405 903 859 992 228 614 971 947 621 730 930 416 592 198 351 68 464 347 505 634 364 663 148 385 836 801 515 915 493 836 543 452 931 395 772 461 689 654 625 16 483 819 788
Выход:
664481 8779 1728829 800375 1926541 436636 272512 794360 1237943 41094 150180 27601 964846 888763 442011 979955 799717 279099 1588154 1421789 1944288 79683 687732 1851177 1754783 706093 1002087 1690021 296284 636364 58576 204764 5419 375448 198625 450938 737167 221753 812718 30739 250692 1342475 1225124 469651 1630287 427113 1342475 526336 354587 1694011 263465 1129495 369081 882688 789434 716388 204 409663 1285603 1180671
У меня было несколько ошибок (код отредактирован 1 раз)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
long long t, n, sum, d[1000010];
int main()
{
cin >> t;
for (int i = 1; i <= t; i ){
cin >> n;
sum = 0;
for (int k = n; k; k--){
d[k] = (n / k) * (n / k);
for (int j = k k; j <= n; j = k)
d[k] -= d[j];
sum = d[k] * k;
}
cout << (sum - n*(n 1)/2)/2 << 'n';
}
}
Конкурс отсюда: http://ntucoder.net/Problem/Details/5610
Комментарии:
1. Хотя это законно, вложение для циклов с использованием одного и того же имени переменной является очень плохой практикой. У вас есть вложенные циклы, определяющие новую копию переменной i.
2. Почти наверняка найдется какой-нибудь математический трюк, который уничтожит большую часть, если не всю, работы. Если вы не знаете или не обнаружите этот трюк, вы не сможете обработать заданный ввод в течение заданного времени или других ограничений ресурсов.
3. @user4581301 Что это за математические трюки?
4. Кажется, что существует способ O(n^(3/2)). Подходит ли это для данных ограничений?
5. используя простую сортировку, вы можете рассчитать все результаты за одно сканирование. и добавляйте к каждому результату только в том случае, если i, j
Ответ №1:
Это поздний ответ после оставления комментариев. Я оглянулся на свой каталог «фрагменты стекового потока» и понял, что реализовал решение для этого вопроса (67689345), и забыл об этом…
Ключ состоит в том, чтобы найти аналитическое выражение для суммы gcd, которое требует факторизации (n) . см.: Функция Пиллаи или: Функция gcd-суммы
Сведение в таблицу всех простых коэффициентов для (n <= 1000000) во время выполнения происходит так быстро, что это почти не влияет на общее время выполнения. Однако я использовал свою утилиту для создания таблицы всех простых (p) <= (1000) чисел . На самом деле он находит все простые числа до (1024) , но это нормально. sp_factor дает простую факторизацию с кратностью, если простой фактор встречается более одного раза, поэтому любые повторяющиеся факторы должны обрабатываться в gcdsum функции. В любом случае они необходимы для показателей первичной мощности.
Примечание: каждый (n) из них учитывается для нахождения суммирования терминов gcd. Мы используем преобразование индекса суммирования, чтобы получить:
Обратите внимание, что суммирование для (n <= 1000000) может превышать 32 бита. Таким образом, используется 64-разрядный аккумулятор. На старом ноутбуке, которым я сейчас пользуюсь, — двухъядерном i7 с частотой 2 ГГц-это занимает менее (0,25) секунды, что должно соответствовать требованиям конкурса.
Результаты для: n = {1, .., 5} соответствуют значениям конкурса: {0, 1, 3, 7, 11} , в то время как: n = 1000000 результаты: 4071628673912
/******************************************************************************/
#include <inttypes.h>
/******************************************************************************/
static const uint16_t sp_lut[] =
{
0x0002, 0x0003, 0x0005, 0x0007, 0x000b, 0x000d, 0x0011, 0x0013,
0x0017, 0x001d, 0x001f, 0x0025, 0x0029, 0x002b, 0x002f, 0x0035,
0x003b, 0x003d, 0x0043, 0x0047, 0x0049, 0x004f, 0x0053, 0x0059,
0x0061, 0x0065, 0x0067, 0x006b, 0x006d, 0x0071, 0x007f, 0x0083,
0x0089, 0x008b, 0x0095, 0x0097, 0x009d, 0x00a3, 0x00a7, 0x00ad,
0x00b3, 0x00b5, 0x00bf, 0x00c1, 0x00c5, 0x00c7, 0x00d3, 0x00df,
0x00e3, 0x00e5, 0x00e9, 0x00ef, 0x00f1, 0x00fb, 0x0101, 0x0107,
0x010d, 0x010f, 0x0115, 0x0119, 0x011b, 0x0125, 0x0133, 0x0137,
0x0139, 0x013d, 0x014b, 0x0151, 0x015b, 0x015d, 0x0161, 0x0167,
0x016f, 0x0175, 0x017b, 0x017f, 0x0185, 0x018d, 0x0191, 0x0199,
0x01a3, 0x01a5, 0x01af, 0x01b1, 0x01b7, 0x01bb, 0x01c1, 0x01c9,
0x01cd, 0x01cf, 0x01d3, 0x01df, 0x01e7, 0x01eb, 0x01f3, 0x01f7,
0x01fd, 0x0209, 0x020b, 0x021d, 0x0223, 0x022d, 0x0233, 0x0239,
0x023b, 0x0241, 0x024b, 0x0251, 0x0257, 0x0259, 0x025f, 0x0265,
0x0269, 0x026b, 0x0277, 0x0281, 0x0283, 0x0287, 0x028d, 0x0293,
0x0295, 0x02a1, 0x02a5, 0x02ab, 0x02b3, 0x02bd, 0x02c5, 0x02cf,
0x02d7, 0x02dd, 0x02e3, 0x02e7, 0x02ef, 0x02f5, 0x02f9, 0x0301,
0x0305, 0x0313, 0x031d, 0x0329, 0x032b, 0x0335, 0x0337, 0x033b,
0x033d, 0x0347, 0x0355, 0x0359, 0x035b, 0x035f, 0x036d, 0x0371,
0x0373, 0x0377, 0x038b, 0x038f, 0x0397, 0x03a1, 0x03a9, 0x03ad,
0x03b3, 0x03b9, 0x03c7, 0x03cb, 0x03d1, 0x03d7, 0x03df, 0x03e5,
0x03f1, 0x03f5, 0x03fb, 0x03fd, 0x0000
};
/* 172 primes < 2^10 factor 83.87% of all odd integers. */
/******************************************************************************/
static inline unsigned int sp_factor (uint32_t p[], uint32_t n)
{
uint32_t sp = sp_lut[0], q;
unsigned int np = 1;
/* assert(n > 1 amp;amp; n < (UINT32_C(1) << (20))); */
for (unsigned int i = 1; (q = n / sp) >= sp; )
{
if (q * sp == n)
np , n = q, *p = sp;
else if ((sp = sp_lut[i ]) == 0) /* EOT entry: */
break;
}
*p = n;
return np; /* the number of prime factors (with multiplicity). */
}
/******************************************************************************/
static uint64_t gcdsum (uint32_t n_max)
{
uint64_t sum = 0;
/* assert(n < (UINT32_C(1) << (20))); */
for (uint32_t n = 2; n <= n_max; n )
{
uint32_t ptab[(20)], pn, gn = 2 * n - 1;
if ((pn = sp_factor(ptab, n)) != 1) /* composite: */
{
uint32_t etab[(20)], un, p, i;
etab[0] = 1, un = 1;
for (p = ptab[0], i = 1; i < pn; i )
{
uint32_t pi = ptab[i];
if (pi == p)
etab[un - 1] ;
else
{
ptab[un] = (p = pi), etab[un] = 1;
un ;
}
}
for (gn = 1, i = 0; i < un; i )
{
uint32_t pi = ptab[i], ei = etab[i];
gn *= ((ei 1) * pi - ei);
while (--ei) gn *= pi; /* pi ^ (ei - 1) */
}
}
sum = gn - n; /* exclude (n, n) term from summation. */
}
return sum;
}
/******************************************************************************/