Trang 4 trên tổng số 4 Đầu tiênĐầu tiên ... 234
Từ 31 tới 37 trên tổng số 37 kết quả

Đề tài: Vòng lặp vô tận

  1. #31
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    843

    Mặc định Vòng lặp vô tận

    Thấy một đề tài bắt ta phải động não thì cũng để chúng ta hiểu thêm mà thôi. Nếu chúng ta thấy theo đuổi là vô vọng, thì chúng ta cũng có thể nói rõ ràng mà.
    Tôi tin ý của bạn, vậy ta đề nghị chủ đề tài sao chép lại bài giải đưa lên diễn đàn để học hỏi, nếu không có là ông thầy đó không có tâm với học trò. Hy vọng ông ấy đọc được.

  2. #32
    Ngày gia nhập
    07 2011
    Bài viết
    448

    edit: hình như ra đáp án rồi: khỏi cần tìm chu kì. Công thức Công thức toán học Latex. 2^t mod (a+b) có thể tính lẹ được => O(log t) là ra đáp án

    C++ Code:
    1. #include <iostream>
    2.  
    3. long long p2mod(int t, int n)
    4. {
    5.     if (t == 0) return 1;
    6.     long long x = 1;
    7.     for (long long k = 2; t; k = k * k % n)
    8.     {
    9.         if (t&1) x = x * k % n;
    10.         t >>= 1;
    11.     }
    12.     return x;
    13. }
    14.  
    15. int main()
    16. {
    17.     int a  = 999999924;
    18.     int b  = 999999937;
    19.     int tt = a + b - 1;
    20.    
    21.     int A = a * p2mod(tt, a+b) % (a+b);
    22.     if (!A) A = a + b;
    23.     std::cout << A << "\n";
    24.    
    25.     int a1 = a, b1 = b;
    26.     for (int t = 0; t < 100; ++t)
    27.     {
    28.         A = a * p2mod(t, a+b) % (a+b);
    29.         if (!A) A = a + b;
    30.         std::cout << A << " " << a1 << "\n";
    31.         if (a1 > b1) { a1 -= b1; b1 *= 2; } else { b1 -= a1; a1 *= 2; }
    32.     }
    33. }

    nó in ra
    Code:
    999999924
    999999924 999999924
    1999999848 1999999848
    1999999835 1999999835
    1999999809 1999999809
    1999999757 1999999757
    1999999653 1999999653
    1999999445 1999999445
    1999999029 1999999029
    1999998197 1999998197
    1999996533 1999996533
    1999993205 1999993205
    1999986549 1999986549
    1999973237 1999973237
    1999946613 1999946613
    1999893365 1999893365
    1999786869 1999786869
    1999573877 1999573877
    1999147893 1999147893
    1998295925 1998295925
    1996591989 1996591989
    1993184117 1993184117
    1986368373 1986368373
    1972736885 1972736885
    1945473909 1945473909
    1890947957 1890947957
    1781896053 1781896053
    1563792245 1563792245
    1127584629 1127584629
    255169397 255169397
    510338794 510338794
    1020677588 1020677588
    41355315 41355315
    82710630 82710630
    165421260 165421260
    330842520 330842520
    661685040 661685040
    1323370080 1323370080
    646740299 646740299
    1293480598 1293480598
    586961335 586961335
    1173922670 1173922670
    347845479 347845479
    695690958 695690958
    1391381916 1391381916
    782763971 782763971
    1565527942 1565527942
    1131056023 1131056023
    262112185 262112185
    524224370 524224370
    1048448740 1048448740
    96897619 96897619
    193795238 193795238
    387590476 387590476
    775180952 775180952
    1550361904 1550361904
    1100723947 1100723947
    201448033 201448033
    402896066 402896066
    805792132 805792132
    1611584264 1611584264
    1223168667 1223168667
    446337473 446337473
    892674946 892674946
    1785349892 1785349892
    1570699923 1570699923
    1141399985 1141399985
    282800109 282800109
    565600218 565600218
    1131200436 1131200436
    262401011 262401011
    524802022 524802022
    1049604044 1049604044
    99208227 99208227
    198416454 198416454
    396832908 396832908
    793665816 793665816
    1587331632 1587331632
    1174663403 1174663403
    349326945 349326945
    698653890 698653890
    1397307780 1397307780
    794615699 794615699
    1589231398 1589231398
    1178462935 1178462935
    356926009 356926009
    713852018 713852018
    1427704036 1427704036
    855408211 855408211
    1710816422 1710816422
    1421632983 1421632983
    843266105 843266105
    1686532210 1686532210
    1373064559 1373064559
    746129257 746129257
    1492258514 1492258514
    984517167 984517167
    1969034334 1969034334
    1938068807 1938068807
    1876137753 1876137753
    1752275645 1752275645
    vậy là đúng hết rồi @_@

    edit: cách mò:
    - để ý thấy mỗi dòng a b đều có tổng bằng nhau, gọi tổng này là hằng số S = a + b
    - như vậy ko cần lưu giá trị của b, chỉ cần a là đủ, b sẽ được tính b = S - a
    - so sánh a > b chuyển thành so sánh a > S/2 (a lớn hơn 1/2 S là a > b)
    - nếu a <= b: a *= a và b -= a, giờ chuyển thành a = 2*a
    - nếu a > b: a -= b và b *= 2, giờ chuyển thành a -= S - a, b ko cần tính
    - a -= S - a viết lại là a = 2*a - S
    - cả 2 trường hợp đều có a = 2*a, chỉ duy nhất a > S/2 là phải trừ S, vậy có thể viết gộp lại, xài phép chia lấy dư: a = 2 * a % S, với trường hợp đặc biệt nếu a = S/2 thì a = S (chứ ko phải 0)
    - Công thức toán học Latex
    - Công thức toán học Latex
    - ...
    - Công thức toán học Latex
    Vậy ta rút ra công thức tổng quát, xét thêm vài trường hợp đặc biệt:
    - nếu Công thức toán học Latex thì Công thức toán học Latex
    - nếu Công thức toán học Latex:
      + nếu Công thức toán học Latex
      + nếu Công thức toán học Latex
    Đã được chỉnh sửa lần cuối bởi INTP : 05-07-2018 lúc 02:19 AM.

  3. #33
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Đúng rồi.

    Mình viết thêm vào code của INTP tý, để dễ dùng hơn cho những giá trị t lớn.

    C++ Code:
    1. // Modified version of http://diendan.congdongcviet.com/threads/t416701::vong-lap-vo-tan.cpp?p=932219#post932219
    2.  
    3. #include <iostream>
    4.  
    5. typedef long long LONG;
    6.  
    7. int p2mod(LONG t, int n)
    8. {
    9.     if (t == 0) return 1;
    10.     LONG x = 1;
    11.     for (LONG k = 2; t; k = k * k % n)
    12.     {
    13.         if (t&1) x = x * k % n;
    14.         t >>= 1;
    15.     }
    16.     return x;
    17. }
    18.  
    19. int mulp2mod(int a, LONG t, int n) {
    20.     return ( LONG(a) * LONG(p2mod(t,n)) % n );
    21. }
    22.  
    23. int main()
    24. {
    25.     int a  = 999999924;
    26.     int b  = 999999937;
    27.     int tt = a + b - 1;
    28.  
    29.     int A = mulp2mod(a,tt,a+b); //a * p2mod(tt, a+b) % (a+b);
    30.     if (!A) A = a + b;
    31.     std::cout << A << "\n";
    32.  
    33.     LONG t0 = LONG(tt)*1000000000-5;
    34.     std::cout << "t0 is" << " " << t0 << "\n";
    35.     int a1 = mulp2mod(a,t0,a+b); // a * p2mod(t0, a+b) % (a+b);
    36.     if (!a1) a1 = a + b;
    37.     int b1 = a + b - a1;
    38.  
    39.     for (LONG t = t0; t < t0+10; ++t)
    40.     {
    41.         A = mulp2mod(a,t,a+b); // a * p2mod(t, a+b) % (a+b);
    42.         if (!A) A = a + b;
    43.         std::cout << A << " " << a1 << "\n";
    44.         if (a1 > b1) { a1 -= b1; b1 *= 2; } else { b1 -= a1; a1 *= 2; }
    45.     }
    46. }
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  4. #34
    Ngày gia nhập
    07 2011
    Bài viết
    448

    rảnh rỗi sinh nông nỗi thử tìm cách tìm chu kì của a b đi

  5. #35
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Phép nhân x với a mod S và sửa kết quả 0 thành S (nếu có) là đơn ánh (trên x). Nên bài toán trở thành tính chu kỳ của dãy 2^t mod S. Có thể liên quan với nhóm nhân mod S. https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n

    - - - Nội dung đã được cập nhật ngày 06-07-2018 lúc 01:31 PM - - -

    Bậc của n (tức chu kỳ của n^t mod S) là ước của lambda S. https://en.wikipedia.org/wiki/Carmichael_function

    Tóm lại, có thể tính [nhanh] được bậc của 2 nếu phân tích được một số cỡ S ra thừa số nguyên tố. Còn cách nào khác (không cần đến thừa phân nguyên tố) mình không biết.
    Đã được chỉnh sửa lần cuối bởi Ada : 06-07-2018 lúc 01:26 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  6. #36
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    495

    Mặc định Vòng lặp vô tận

    Edit: lambda(S), vốn chứa n^t mod S, xác định cho các giá trị n nguyên tố cùng nhau với S, nên nói thật chính xác, khi xem xét dãy 2^t mod S, gọi s là ước lẻ lớn nhất của S, phân tích S thành S = s*2^k (k là số tự nhiên) thì:

    (1) độ dài chu kỳ là một ước nào đó của lambda(s). Nói riêng, chu kỳ có độ dài S-1 chỉ khi S là số nguyên tố.

    (2) chu kỳ bắt đầu từ phần tử thứ k của dãy. Nói riêng, nếu S là số lẻ (k=0), chu kỳ bắt đầu ngay từ phần tử đầu tiên.

    (Và với dãy a*2^t mod S của bài tập này, chu kỳ bắt đầu từ một vị trí nào đó không quá k).
    Đã được chỉnh sửa lần cuối bởi Ada : 08-07-2018 lúc 01:08 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  7. #37
    Ngày gia nhập
    07 2011
    Bài viết
    448

    S = s*2^k thì có thể chu kỳ bắt đầu từ phần tử thứ nhỏ hơn k, ví dụ 2 8 chẳng hạn: S là 10 = 2^1 * 5, chu kì lại bắt đầu từ index 0 chứ ko phải 1. Phải chia gcd(a, S) (hoặc gcd(a,b)) cho S nữa, rồi mới tách 2^k' ra.



    Gọi Công thức toán học Latex là phần tử thứ nhất của chu kì đầu tiên, Công thức toán học Latex là độ dài chu kì. Ta có:
    Công thức toán học Latex

    Công thức toán học Latex, ta có:
    Công thức toán học Latex

    Hay ta có thể viết lại thành Công thức toán học Latex với Công thức toán học Latex là một số nguyên không âm nào đó.

    Gọi Công thức toán học Latex = UCLN của Công thức toán học LatexCông thức toán học Latex. Ta có thể viết Công thức toán học Latex, Công thức toán học Latex, với Công thức toán học Latex, Công thức toán học Latex là số nguyên không âm, và Công thức toán học Latex, Công thức toán học Latex nguyên tố cùng nhau. ta có Công thức toán học Latex. Phương trình ở trên rút gọn lại thành: Công thức toán học Latex

    Công thức toán học LatexCông thức toán học Latex nguyên tố cùng nhau, Công thức toán học Latex phải chia hết cho Công thức toán học Latex. Đặt Công thức toán học LatexCông thức toán học Latex, ta có:
    Công thức toán học Latex

    Công thức toán học Latex lẻ, nếu ta viết Công thức toán học Latex lại thành Công thức toán học Latex, với Công thức toán học Latex, Công thức toán học Latex là số nguyên không âm, thì Công thức toán học Latex phải chia hết cho Công thức toán học Latex , và Công thức toán học Latex phải chia hết cho Công thức toán học Latex, hay Công thức toán học Latex. Vì Công thức toán học Latex là phần tử thứ nhất của chu kì đầu tiên nên Công thức toán học Latex phải là số nhỏ nhất, hay Công thức toán học Latex.

    Công thức toán học Latex chia hết cho Công thức toán học Latex nghĩa là Công thức toán học Latex. Vì Công thức toán học Latex lẻ nên nó không chia hết cho Công thức toán học Latex, hay Công thức toán học LatexCông thức toán học Latex nguyên tố cùng nhau. Vậy ta có thể dùng Carmichael function để tìm Công thức toán học Latex là số nguyên dương nhỏ nhất sao cho Công thức toán học Latex với mọi Công thức toán học Latex nguyên tố cùng nhau với Công thức toán học Latex. Ở đây ta chỉ cần tìm Công thức toán học Latex là số mũ nhỏ nhất với Công thức toán học Latex, nên Công thức toán học Latex phải là ước nhỏ nhất của Công thức toán học Latex sao cho Công thức toán học Latex.


    code C++14:
    C++ Code:
    1. #include <iostream>
    2. #include <cmath>
    3. #include <cstdint>
    4. #include <utility>
    5. #include <algorithm>
    6.  
    7. inline int gcd(int a, int b)
    8. { while (b) a = std::exchange(b, a % b); return a; }
    9.  
    10. inline int lcm(int a, int b)
    11. { return a / gcd(a, b) * b; }
    12.  
    13. int32_t modPow(int32_t base, int32_t exponent, int32_t modulus)
    14. {
    15.     int64_t result = 1, exp = exponent;
    16.     for (base %= modulus; exp > 0; exp >>= 1, base = base * base % modulus)
    17.         if (exp & 1) result = result * base % modulus;
    18.     return static_cast<int32_t>(result);
    19. }
    20.  
    21. template <class BinaryFunction>
    22. void forEachPrimeFactorPower(int n, BinaryFunction&& f)
    23. {
    24.     int sqrtn = static_cast<int>(std::sqrt(n));
    25.     for (int p = 2, r = 0; p <= sqrtn; ++p)
    26.         if (n % p == 0)
    27.         {
    28.             for (r = 0; n % p == 0; n /= p) ++r;
    29.             f(p, r);
    30.             sqrtn = static_cast<int>(std::sqrt(n));
    31.         }
    32.     if (n != 1) f(n, 1);
    33. }
    34.  
    35. int carmichaelFunction(int n)
    36. {
    37.     int N = 1;
    38.     forEachPrimeFactorPower(n, [&N](int p, int r) {
    39.         N = lcm(N, static_cast<int>(std::pow(p, r - 1)) * (p - 1));
    40.     });
    41.     return N;
    42. }
    43.  
    44. template <class UnaryFunction>
    45. void forEachDivisor(int n, UnaryFunction&& f)
    46. {
    47.     int sqrtn = static_cast<int>(std::sqrt(n));
    48.     if (sqrtn * sqrtn == n) f(sqrtn--);
    49.     for (int d = 1; d <= sqrtn; ++d)
    50.         if (n % d == 0) { f(d); f(n / d); }
    51. }
    52.  
    53. int main()
    54. {
    55.     int a, b;
    56.     std::cin >> a >> b;
    57.     int s = (a + b) / gcd(a, b);
    58.     // Find m
    59.     int m = 0;
    60.     for (; s % 2 == 0; s /= 2) ++m;
    61.     // Find n
    62.     int N = carmichaelFunction(s);
    63.     int n = N;
    64.     forEachDivisor(N, [&n, s](int d) {
    65.         if (modPow(2, d, s) == 1) n = std::min(n, d);
    66.     });
    67.     std::cout << m << " " << n << "\n";
    68. }

Trang 4 trên tổng số 4 Đầu tiênĐầu tiên ... 234

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn