-Поиск по дневнику

Поиск сообщений в rss_forum_sources_ru

 -Подписка по e-mail

 

 -Постоянные читатели

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 29.07.2007
Записей:
Комментариев:
Написано: 80


Поиск минимального числа при условии

Среда, 08 Июля 2020 г. 16:07 + в цитатник
JoeUser: Ну а я перевел все на НОДы/НОКи, получилось для первого набора вот так:
Скрытый текст
    #include
    #include
    #include
    #include "BigIntegerLibrary.hh"
    std::vector R;
    BigInteger Nod(BigInteger a, BigInteger b) {
    while (a != 0 and b != 0) if (a > b) a %= b; else b %= a;
    return a+b;
    }
    BigInteger Nok(BigInteger a, BigInteger b) {
    return a/Nod(a,b)*b;
    }
    void YouTest(std::vector &V) {
    BigInteger M;
    for(size_t i=0; i+1div>
    if (i==0) M = Nok(V[0],V[1]); else M = Nok(M,V[i+1]);
    }
    R.push_back(M);
    }
    void Func() {
    std::vector> Arr = {
    {0x0003,0x0004,0x000d,0x0017,0x001b,0x001d,0x0021,0x0022,0x01d2,0x01d6},
    {0x0001,0x000b,0x000c,0x000d,0x000e,0x0012,0x0019,0x001d,0x01bd,0x01c6},
    {0x0001,0x000d,0x000e,0x0015,0x0023,0x0028,0x002c,0x002e,0x01d2,0x01d5},
    {0x0006,0x000b,0x0012,0x0015,0x0019,0x001c,0x001f,0x0027,0x01b2,0x01c1},
    {0x0003,0x0009,0x000d,0x000e,0x0010,0x0012,0x0013,0x0015,0x01d5,0x01d6},
    {0x0007,0x0009,0x000f,0x0018,0x001a,0x001c,0x001e,0x0028,0x01ca,0x01cb},
    {0x0004,0x0008,0x0011,0x0014,0x0018,0x001b,0x001e,0x0028,0x01b9,0x01ba},
    {0x0008,0x0011,0x0024,0x0027,0x0031,0x0037,0x0038,0x003c,0x01b5,0x01bd},
    {0x0003,0x0004,0x0006,0x000a,0x000b,0x0010,0x0013,0x0019,0x01bf,0x01c1},
    {0x0005,0x0006,0x0009,0x000c,0x001f,0x0027,0x0028,0x002f,0x01c1,0x01cd},
    {0x0003,0x0004,0x0006,0x0007,0x0016,0x0019,0x001c,0x001d,0x01db,0x01dc},
    {0x0002,0x0009,0x000c,0x0012,0x0013,0x0014,0x0018,0x001f,0x01b9,0x01bb},
    {0x000d,0x0010,0x0017,0x001e,0x001f,0x0021,0x0023,0x002d,0x01c3,0x01c4},
    {0x0002,0x0005,0x0007,0x000a,0x000e,0x0010,0x0014,0x0015,0x01c6,0x01c7},
    {0x0001,0x0002,0x0009,0x000d,0x0013,0x0018,0x001a,0x0024,0x01cd,0x01cf},
    {0x0008,0x000b,0x000f,0x0014,0x0016,0x001c,0x0021,0x0029,0x01c5,0x01c8},
    {0x0007,0x000b,0x000e,0x0010,0x0012,0x0016,0x0025,0x002e,0x01d8,0x01dd},
    {0x0007,0x0008,0x000f,0x0011,0x0022,0x0028,0x002b,0x0036,0x01c1,0x01c4},
    {0x0003,0x0019,0x0021,0x0022,0x0029,0x0031,0x0034,0x0036,0x01bf,0x01c2},
    {0x0002,0x0004,0x0006,0x000d,0x0010,0x0011,0x0012,0x0015,0x01cb,0x01ce},
    {0x0001,0x0007,0x000d,0x0012,0x0022,0x0024,0x002a,0x002f,0x01cf,0x01d0},
    {0x0001,0x0002,0x0008,0x0009,0x000b,0x000c,0x000d,0x0010,0x01c1,0x01c8},
    {0x000b,0x000e,0x000f,0x0015,0x001b,0x001d,0x0021,0x0023,0x019c,0x019f},
    {0x0002,0x0004,0x000f,0x0012,0x0015,0x0016,0x001f,0x0020,0x01b6,0x01c4},
    {0x0002,0x0006,0x0008,0x000b,0x0019,0x0032,0x0037,0x003a,0x01c8,0x01c9},
    {0x0001,0x0005,0x0008,0x0009,0x000d,0x0011,0x0012,0x0013,0x01d5,0x01db},
    {0x0001,0x0003,0x0004,0x0005,0x000b,0x0012,0x0014,0x001a,0x01c3,0x01c4},
    {0x0001,0x000b,0x0010,0x001d,0x0021,0x0028,0x002a,0x0036,0x01c1,0x01c2},
    {0x0002,0x0008,0x000b,0x000e,0x000f,0x0013,0x001f,0x0021,0x01d9,0x01dc},
    {0x0004,0x0009,0x0011,0x001c,0x001d,0x0027,0x0029,0x0033,0x01cc,0x01ce},
    {0x0003,0x000c,0x000d,0x0016,0x0017,0x001a,0x001b,0x0020,0x01be,0x01c7},
    {0x0008,0x000c,0x000e,0x0010,0x0017,0x0019,0x001c,0x001d,0x01a2,0x01b0}
    };
    for (auto &&i:Arr) YouTest(i);
    }
    int main() {
    R.reserve(32*1024);
    auto start = std::chrono::high_resolution_clock::now();
    for(int i=0; i<1024; i++) Func();
    auto stop = std::chrono::high_resolution_clock::now();
    std::cout << "Elapsed: "
    << std::chrono::duration_cast(stop - start).count()
    << " ms"
    << std::endl;
    for(int i=0; i<32; i++) std::cout << R[i] << std::endl;
    std::cout << std::endl;
    return 0;
    }

вывод:
Скрытый текст
    Elapsed: 1378 ms
    9588669098580
    527825598300
    43129446360
    12539627100
    3920127120
    382604040
    11695320
    1667842296120
    16778770800
    1411408313640
    216377700
    4602752280
    2380775276880
    4957680
    3795870312
    1086891960
    29506021776
    280390927320
    1964784521700
    7351344
    140581978992
    175670352
    10308555180
    28354122720
    1661926200
    3544795800
    119253420
    10828263600
    3978365160
    83765501820
    22179437280
    10538866800

А для второго набора с большими числами изначально
Скрытый текст
    std::vector> Arr = {
    {0x7cd45dd6,0x7cfb2c2f,0x7d17697c,0x7d1c4aed,0x7d1e29e1,0x7d5766ed,0x7dee7bbd,0x7dff2159,0x7e007b27,0x7e045db9},
    {0x7d710637,0x7d720e66,0x7d8a5328,0x7dae46b1,0x7de0429c,0x7df70761,0x7e072d36,0x7e146be0,0x7e320e0b,0x7e51405c},
    {0x7d59173e,0x7d5b6f43,0x7d5f73af,0x7d651a54,0x7d7555e4,0x7d7f206d,0x7dab0f4f,0x7db11276,0x7dbd4b37,0x7ddc79ad},
    {0x7d0125e7,0x7d191867,0x7d1d42f9,0x7d226efd,0x7d2b223a,0x7d357524,0x7d5c17e8,0x7d8e5293,0x7d9e6e53,0x7ddd7053},
    {0x7d6550cf,0x7dd00b81,0x7de6495f,0x7df4279c,0x7e042f64,0x7e461e67,0x7e482342,0x7e7e3c7d,0x7e866b20,0x7e9c1d10},
    {0x7e113111,0x7e1f2a68,0x7e252112,0x7e2902f2,0x7e5f78a4,0x7e784d46,0x7ebe3d96,0x7ec82d4e,0x7ecb53c4,0x7edf4c73},
    {0x7d26032a,0x7d2b20c6,0x7d3a5c2e,0x7d5354ee,0x7d882b72,0x7d921cc1,0x7d9b4027,0x7e032f12,0x7e6c09d3,0x7e7d7ed5},
    {0x7bf657d5,0x7c014a70,0x7c4506a2,0x7cd329f0,0x7ce56aa7,0x7ce81d34,0x7d1716f4,0x7d194dc6,0x7d23131a,0x7d5e3664},
    {0x7d496f5d,0x7d4c0f41,0x7d606b1a,0x7d6461d0,0x7d6c6be0,0x7d717a80,0x7e096d25,0x7e106047,0x7e780539,0x7e937878},
    {0x7d24062e,0x7d2c6b82,0x7d827250,0x7da12d0c,0x7dc12285,0x7dc63b60,0x7dc822c7,0x7dd41f99,0x7e0f3c28,0x7e456330},
    {0x7c6f6e37,0x7c9f7469,0x7ca94be5,0x7ccb31bb,0x7ce2198d,0x7ceb40b5,0x7d0267e9,0x7d524e46,0x7d6f0ba7,0x7d7f0a37},
    {0x7d2c3397,0x7d2c38bd,0x7dd62c04,0x7dd67b90,0x7df64421,0x7e0c6b08,0x7e227887,0x7e3e7bed,0x7e410fc6,0x7e477b3c},
    {0x7cc30907,0x7cd60b0b,0x7cef020a,0x7d03001c,0x7d2c64a3,0x7d350179,0x7d4b41e5,0x7d856488,0x7d9c0c74,0x7dd54e69},
    {0x7c1f748c,0x7c21175f,0x7c6238fb,0x7c82171b,0x7cad08ed,0x7cb24149,0x7ce94757,0x7d036ae4,0x7d214b58,0x7d6f0a3d},
    {0x7d416876,0x7d690162,0x7d7015c9,0x7d88180b,0x7dc04b25,0x7dd363fa,0x7df9418e,0x7e094c2a,0x7e26677c,0x7e55473c},
    {0x7d345112,0x7d397f62,0x7d537af7,0x7d58312a,0x7d6727d4,0x7d9e59aa,0x7dcd116d,0x7dcf192c,0x7dd95b41,0x7df76402},
    {0x7d5c2fb5,0x7d863062,0x7d995475,0x7da67b0b,0x7dcf14ae,0x7df00bfb,0x7e042300,0x7e2b1ab9,0x7e477f1e,0x7e725a93},
    {0x7dfc4f7f,0x7e037475,0x7e1c3261,0x7e2f60e1,0x7e3d3d85,0x7e421fcc,0x7e6540de,0x7e67531a,0x7e7d6cc7,0x7e7f0789},
    {0x7d057a8c,0x7d07099d,0x7d14041a,0x7d207534,0x7d2b1875,0x7d4e32c8,0x7d5112ea,0x7d64127d,0x7dc1228e,0x7dd0732e},
    {0x7d664f54,0x7db1778d,0x7dda61a7,0x7de51343,0x7df63b84,0x7e0605db,0x7e081bda,0x7e184611,0x7e624928,0x7e640832},
    {0x7e7842b9,0x7e9f4ad6,0x7ea64ecc,0x7eb7125d,0x7ebc47b1,0x7ecc3d4a,0x7ed53815,0x7edc2062,0x7edc276d,0x7eee4861},
    {0x7d014c60,0x7d0b0920,0x7d3554bd,0x7d627ca5,0x7d6415ac,0x7d647a60,0x7d9f722a,0x7dfc3598,0x7e213d60,0x7e3a2b78},
    {0x7cd92864,0x7d33706f,0x7d8e2363,0x7dc10eb5,0x7dd55002,0x7e2c7cd1,0x7e447327,0x7e457cbe,0x7e6d6f27,0x7e73533e},
    {0x7cf01896,0x7d172b41,0x7d5a79b3,0x7d89255c,0x7deb4f3f,0x7df974e4,0x7dff01cd,0x7e5c1595,0x7e7279d5,0x7e7c2d05},
    {0x7c926328,0x7ca004e9,0x7cad57ec,0x7ce9775f,0x7cf7135d,0x7d07453c,0x7d084c8b,0x7d0f6b4c,0x7d454c67,0x7d4f3a45},
    {0x7e2e57f8,0x7e3f6b7b,0x7e5370c3,0x7e764d44,0x7e8a5f0c,0x7e8c3417,0x7ea060b4,0x7eab0a71,0x7ec4369d,0x7ecd2d1a},
    {0x7cad0fb7,0x7cc477d0,0x7cc74a4c,0x7ce71c30,0x7d20003c,0x7d2b1b78,0x7d735951,0x7d9741d6,0x7da77b9f,0x7dc90f2e},
    {0x7c9d3798,0x7c9e535f,0x7ca844b9,0x7cad10b6,0x7cb56f5a,0x7d0209d0,0x7d1b40c7,0x7d1b617b,0x7d710abf,0x7d722c3e},
    {0x7d847bb6,0x7de5361b,0x7e1e6471,0x7e223fd8,0x7e340c2b,0x7e5c4c1a,0x7e7445c6,0x7e760312,0x7e7f2cce,0x7e894d2e},
    {0x7d493a94,0x7d4f528a,0x7d7f3e2f,0x7d875f25,0x7dbd50a8,0x7de851c6,0x7e335209,0x7e385ccc,0x7e482cc0,0x7e48798a},
    {0x7c7c1b24,0x7cf13502,0x7d534047,0x7d584c31,0x7d5b53c6,0x7d6b5ee1,0x7daa4f8f,0x7de2717a,0x7dea4786,0x7dff7af7},
    {0x7d1871a4,0x7d2018bd,0x7d2815cd,0x7d774b76,0x7d841cd9,0x7d895b6d,0x7dd76085,0x7df34d8b,0x7dfe45d9,0x7dfe4d99}
    };

Получился вот такой результат:
Скрытый текст
    Elapsed: 7813 ms
    8365952198818774082761182752826492709705353472768857783518932270943615384126743225484220
    6320784966646816085566075372050288774163083533310223412067630401536400391507483003360
    372965641708056343100671012886426814882051314151484963188075362084382390495188874300
    152046970479457502245073922096275168909385354426662178417039241800071420492281361373952680
    126527352355773471721414839256668398843177001156445305761310662173112181954910210287456
    103173769752087961922560643530764147207112796208249628740374208211004747481026394897960
    97580947841540309585744501944268707806192013625089179078240251275199492717354127494050410
    658424750501043684868086106460183123310519659236268731747507021965953665328766603600
    219526365178587019702964440217431588833431189719850964824263190628965911597070052480
    5896282002515888839350031734886929524119790897492373106113264797010617740512533627939040
    12147216871546784182869018501023272553426670323282399316976611747028891817282129272967380170
    106296206725973511003071955573025894114919643976191842733704315889020489983063580280240
    5167872557586608191948556334010077457643088059745349539962505228671962363637573060206920
    446224936219092299774695846181984522639964926306878449710518868824542371977224101649099720
    440123142671612922643968887481816571303358017322824654791040478709721423143801134896260
    9119713839306100061487001655155324259599019842429627086510112885658955607460594927316
    290517572508361811488661447420828423401260402380137586777930494515519844500267299116800
    50520924027731474619464147641100856895295982212232157980554181149167031553624724765871315172
    4328567320666505347271561328359181982055970787586959933970942463427025802943796550596760
    12952281244141561307406306392058785642677315080032779441231055316800005185073173244452600
    276394662419827287242992857333387035616294952602445960883488304840638048759071430885333500
    696504066204039086504093430337009155728188927832176955004778788831336847216836079200
    6615279929305400025297732430650553553078662258832596392260358097614118819200154375784100
    43878260208418628823156222649970651587385088857268281774469306331890408122270063159410006740
    218787285695220121127373807803078072214370551512233159301622720209468796642905853420158760
    51055566993622631458771818230502965458972847923195223488796602092223024703817681371880
    20141264573928462505142539000000831107750484193507850672036969242867600868875150143440
    156834931714649030815630944760386489262784627499294812061727382540624786877284828530800
    69087642384679507706012918384628597974549327733541898202352422921110101087636970883000
    2694163307667579202220636480509744380958601600596803923780055098580309018684009954974016
    13749346721233841734887885146491926944389137693673390982571052279064803140884657724910260
    148293055169307720833926985648257182289595114441389459016963339316768729714260354703849300

Да, конечно цифры получаются большими.

https://forum.sources.ru/index.php?showtopic=419125&view=findpost&p=3834022

Метки:  

 

Добавить комментарий:
Текст комментария: смайлики

Проверка орфографии: (найти ошибки)

Прикрепить картинку:

 Переводить URL в ссылку
 Подписаться на комментарии
 Подписать картинку