Nếu chúng ta là người yêu thích competitive programming thì bao gồm lẽ các bạn sẽ không kỳ lạ gì với con số này, nó lộ diện thường xuyên trong số cuộc thi. Đến nỗi, các bạn coi nó như một mặc định mà ko phải đề ý.
Bạn đang xem: 1e9 bằng bao nhiêu
Cho mang đến một ngày mình bắt gặp câu hỏi tại sao lại chọn con số (10^9+7) này nhằm tính modulo, bản thân ngớ người và vội vàng đi tìm đáp án.
Đó thực sự là một trong con số quánh biệt: 1000000007, nó là một số nguyên tố. Dẫu vậy đó không phải là tất cả, mình sẽ lý giải tại sao fan ta lại sử dụng modulo và lý do lại dùng số nguyên tố.
Lý do
Có 2 lý do cơ phiên bản cho việc sử dụng modulo (10^9+7) :
Để kiêng các đo lường bị overflow.Để việc đo lường và thống kê trở nên dễ dàng và đơn giản hơn.1. Để tránh việc giám sát bị overflow
Kiểu dữ liệu lớn số 1 trong C/C++ là unsigned long long, bao gồm độ lớn 64 bit, tức là nó trình diễn được những con số trường đoản cú 0 tính đến (2^64 - 1).
Nhưng trong tương đối nhiều bài toán ta nên phải đo lường và thống kê các công dụng lớn hơn tương đối nhiều con số này, cho nên vì vậy ta đề xuất làm bé dại việc giám sát đi cho tương xứng với kiểu tài liệu của chúng ta, đó đó là lý vị của việc thực hiện phép tính modulo.
Điều này giúp bạn cũng có thể tập trung toàn thể vào việc thi công và search kiếm thuật toán, thay do loanh xung quanh implement những phép toán so với số lớn.
Và 1000000007 là một số đủ lớn để sau khi tính modulo, phép toán vừa trở nên đơn giản và dễ dàng lại không biến thành tràn số. Cầm thể:
Phép cộng: ((A+B)mod m = Amod m + Bmod m)Phép trừ: ((A-B)mod m = (Amod m - Bmod m + m)mod m)Phép nhân: ((A imes B)mod m = (Amod m imes Bmod m)mod m).Chú ý một điều là ((10^9+7)^2) trọn vẹn 63 bits, nghĩa là phù hợp với kiểu tài liệu long long, chính vì vậy ta trả toàn rất có thể nhân mà không phải lo ngại tràn số.
Phép chia: tại đây phát sinh vấn đề, đó là lý do tại sao tín đồ ta chọn số nguyên tố, ta đang nói rõ hơn ở bên dướiPhép luỹ thừa: ((A^B)mod m=(A^Bmod (m-1))mod m)2. Để việc đo lường và tính toán trở nên dễ dàng hơn
(10^9+7) là một số nguyên tố.
Rất các phép toán trở nên dễ dàng và đơn giản hơn khi làm việc với số nguyên tố.
Với phép chia, ta phải chăm chú một điều là:
biểu thức đúng đề nghị là:
trong kia (inv(B)) là nghịch đảo theo modulo m của B.
Ta để ý ở đó là nghịch hòn đảo theo modulo (modular multiplicative inverse), chứ chưa phải nghịch đảo đơn thuần trong tính toán thập phân là (frac1B).
Nếu trong đo lường và thống kê thập phân (B imes frac1B = 1) thì theo modulo (B imes inv(B) equiv 1 mod m).
Ví dụ nghịch hòn đảo của 2 trong đo lường và thống kê thập phân là (frac12) vì chưng (2 imes frac12 = 1). Tuy nhiên nghịch hòn đảo theo modulo 5 của 2 đang là 3 vày (2 imes 3 = 6 equiv 1 mod 5). Vậy (inv(2) = 3 mod 5).
Đây là phần kỹ năng và kiến thức khá quan trọng, cùng được sử dụng rất nhiều trong mã hoá, các chúng ta cũng có thể tự tham khảo thêm theo liên kết trên.
Vậy làm nỗ lực nào để tính (inv(B)mod m) ? Đây đó là lúc số nguyên tố mô tả vai trò.
Theo định lý nhỏ tuổi Fermat, giả dụ (m) là một số nguyên tố cùng (B) không chia hết cho (m) thì ta có:
Bằng phép thay đổi này ta đã đưa modulo của phép phân chia trở về modulo của phép nhân và có thể tính toán một cách đối kháng giản.
Kết luận
Tóm lại, số lượng (10^9+7) hay 1000000007 là một con số sệt biệt, nó đầy đủ lớn, và nhằm mục đích dễ dàng tính toán trong các bài toán lập trình.
Theo mọi gì đã chứng minh bên trên thì những số yếu tắc đủ to trong phạm vi (2^30) đều rất có thể thoả mãn, nhưng chắc rằng (10^9+7) là một số có phương pháp viết thuận mắt và đẹp đẽ nhất.
Tham khảo
What exactly is print it modulo 10^9 + 7 in competitive programming web sites?How bởi vì I output modulo 10^9 + 7 in competitive programming?Modulo 10^9+7 (1000000007)Nếu các bạn là người yêu thích competitive programming thì tất cả lẽ bạn sẽ không kỳ lạ gì với con số này, nó lộ diện thường xuyên trong các cuộc thi. Đến nỗi, bạn coi nó như một mang định mà chẳng hề đề ý.
Cho mang đến một ngày mình phát hiện câu hỏi nguyên nhân lại chọn số lượng (10^9+7) này để tính modulo, mình ngớ tín đồ và cấp vàng đi kiếm đáp án.
Đó thực sự là một trong những con số quánh biệt: 1000000007, nó là một trong số nguyên tố. Mà lại đó không phải là tất cả, mình sẽ giải thích tại sao bạn ta lại sử dụng modulo và lý do lại cần sử dụng số nguyên tố.
Lý do
Có 2 lý do cơ bản cho việc thực hiện modulo (10^9+7) :
Để né các đo lường bị overflow.Để việc giám sát và đo lường trở nên dễ dàng hơn.1. Để kị việc giám sát bị overflow
Kiểu dữ liệu lớn số 1 trong C/C++ là unsigned long long, tất cả độ to 64 bit, có nghĩa là nó màn biểu diễn được những con số từ bỏ 0 cho tới (2^64 - 1).
Nhưng trong vô số nhiều bài toán ta phải phải giám sát và đo lường các công dụng lớn hơn không ít con số này, cho nên vì vậy ta cần làm nhỏ việc giám sát đi cho tương xứng với kiểu dữ liệu của bọn chúng ta, đó đó là lý bởi của việc sử dụng phép tính modulo.
Điều này giúp bạn có thể tập trung toàn thể vào việc thiết kế và tìm kiếm thuật toán, thay do loanh quanh implement những phép toán so với số lớn.
Và 1000000007 là một số đủ lớn để sau thời điểm tính modulo, phép toán vừa trở nên dễ dàng lại không trở nên tràn số. Gắng thể:
Phép cộng: ((A+B)mod m = Amod m + Bmod m)Phép trừ: ((A-B)mod m = (Amod m - Bmod m + m)mod m)Phép nhân: ((A imes B)mod m = (Amod m imes Bmod m)mod m).Chú ý một điều là ((10^9+7)^2) hoàn toản 63 bits, nghĩa là phù hợp với kiểu dữ liệu long long, chính vì như vậy ta hoàn toàn có thể nhân mà không lo tràn số.
Phép chia: tại đây nảy sinh vấn đề, kia là tại sao tại sao fan ta chọn số nguyên tố, ta sẽ nói rõ rộng ở mặt dướiPhép luỹ thừa: ((A^B)mod m=(A^Bmod (m-1))mod m)2. Để việc đo lường trở nên đơn giản hơn
(10^9+7) là một số trong những nguyên tố.
Rất các phép toán trở nên đơn giản dễ dàng hơn khi làm việc với số nguyên tố.
Với phép chia, ta phải chú ý một điều là:
biểu thức đúng đề nghị là:
trong đó (inv(B)) là nghịch đảo theo modulo m của B.
Ta xem xét ở đó là nghịch đảo theo modulo (modular multiplicative inverse), chứ chưa hẳn nghịch đảo đơn thuần trong đo lường thập phân là (frac1B).
Nếu trong tính toán thập phân (B imes frac1B = 1) thì theo modulo (B imes inv(B) equiv 1 mod m).
Ví dụ nghịch hòn đảo của 2 trong đo lường và thống kê thập phân là (frac12) vì chưng (2 imes frac12 = 1). Nhưng nghịch hòn đảo theo modulo 5 của 2 đã là 3 vì (2 imes 3 = 6 equiv 1 mod 5). Vậy (inv(2) = 3 mod 5).
Đây là phần kỹ năng và kiến thức khá quan tiền trọng, và được sử dụng tương đối nhiều trong mã hoá, các chúng ta cũng có thể tự bài viết liên quan theo link trên.
Vậy làm rứa nào nhằm tính (inv(B)mod m) ? Đây đó là lúc số nguyên tố thể hiện vai trò.
Theo định lý nhỏ tuổi Fermat, nếu (m) là một trong những nguyên tố với (B) không phân tách hết mang lại (m) thì ta có:
Bằng phép biến hóa này ta đã gửi modulo của phép chia trở về modulo của phép nhân và hoàn toàn có thể tính toán một cách đơn giản.
Kết luận
Tóm lại, con số (10^9+7) hay 1000000007 là một trong con số quánh biệt, nó đầy đủ lớn, và nhằm mục đích đơn giản dễ dàng tính toán trong các bài toán lập trình.
Xem thêm: Đề Cương Ôn Tập Toán 12 Năm 2021, Đề Cương Ôn Thi Học Kì 1 Toán 12 Năm 2021
Theo hầu hết gì đã chứng minh trên thì các số thành phần đủ béo trong phạm vi (2^30) đều có thể thoả mãn, nhưng có lẽ (10^9+7) là một số có biện pháp viết thuận mắt và xinh xắn nhất.
Tham khảo
What exactly is print it modulo 10^9 + 7 in competitive programming web sites?How vì I output đầu ra modulo 10^9 + 7 in competitive programming?Modulo 10^9+7 (1000000007)Video liên quan
Reply 5 0 share