12.1 mod และคำตอบที่ใหญ่เกิน

น้องใช้ % มาตั้งแต่บทที่ 1 ทั้งแยกหลัก ตรวจเลขคู่ และแปลงเวลา หน้านี้ต่อจากตรงนั้นสามเรื่อง เรื่องแรกคือ % กับเลขติดลบที่ให้ผลไม่เหมือนในห้องเรียนคณิตศาสตร์ เรื่องที่สองคือโจทย์ที่คำตอบใหญ่เกิน long long แล้วสั่งว่า "ตอบเป็นเศษจากการหารด้วย 1000000007" ซึ่งเจอบ่อยมากในโจทย์นับจำนวนวิธี และเรื่องสุดท้ายคือยกกำลังเลขชี้กำลังระดับ 10¹⁸ ให้เสร็จในเสี้ยววินาที

หารและ mod เมื่อมีเลขติดลบ

ในหน้า 1.2 เราเห็นแล้วว่าเลขติดลบกับ % ต้องระวัง คราวนี้ดูให้ครบทุกแบบของเครื่องหมาย

#include <stdio.h>

int main()
{
    printf("%d %d\n", 7 / 3, 7 % 3);
    printf("%d %d\n", -7 / 3, -7 % 3);
    printf("%d %d\n", 7 / -3, 7 % -3);
    printf("%d %d\n", -7 / -3, -7 % -3);
    return 0;
}

2 1
-2 -1
-2 1
2 -1

ภาษา C ตั้งแต่มาตรฐาน C99 เป็นต้นมา ซึ่งรวมถึง GCC ที่เราใช้ ทำตามกฎสองข้อนี้ทุกเครื่อง

1. ผลหารตัดทศนิยมทิ้งไปทาง 0 -7 / 3 คือ -2.33 ตัดเหลือ -2 ไม่ใช่ -3
2. เศษมีเครื่องหมายตามตัวตั้ง ตัวตั้งคือเลขที่อยู่หน้า % ตัวตั้งติดลบ เศษก็ติดลบหรือเป็น 0

สองข้อนี้มาคู่กันเพื่อให้ความสัมพันธ์ a == (a / b) * b + a % b เป็นจริงเสมอ ลองแทน a = -7 กับ b = 3 จะได้ (-2) × 3 + (-1) = -7 พอดี

แต่ในวิชาคณิตศาสตร์ เศษต้องอยู่ระหว่าง 0 ถึง b - 1 เสมอ -7 หารด้วย 3 จึงเขียนเป็น -7 = 3 × (-3) + 2 เศษคือ 2 ไม่ใช่ -1 โจทย์ที่ถามเรื่องวนรอบ เช่น วันในสัปดาห์ ชั่วโมงบนหน้าปัดนาฬิกา หรือที่นั่งรอบโต๊ะกลม ต้องการเศษแบบคณิตศาสตร์ ถ้าใช้ % ตรงๆ กับเลขติดลบจะได้ตำแหน่งที่ไม่มีอยู่จริง

ทำให้ mod เป็นบวก

ให้วันอาทิตย์เป็นวันที่ 0 จันทร์เป็น 1 ไปจนถึงเสาร์เป็น 6 วันนี้วันพุธ (3) ถามว่า 12 วันก่อนเป็นวันอะไร

#include <stdio.h>

int main()
{
    int today, shift;
    scanf("%d %d", &today, &shift);
    printf("plain %%  : %d\n", (today + shift) % 7);
    printf("fixed     : %d\n", ((today + shift) % 7 + 7) % 7);
    return 0;
}

3 -12

plain %  : -2
fixed     : 5

3 - 12 = -9 ใช้ % ตรงๆ ได้ -2 ซึ่งไม่ใช่วันไหนเลย บรรทัดที่ 8 แก้ด้วยสามจังหวะ

% 7 รอบสองมีไว้สำหรับค่าที่เป็นบวกอยู่แล้ว ถ้าไม่มี 15 จะกลายเป็น 8 ซึ่งเกิน 6 ไป วันที่ 5 คือวันศุกร์ ตรวจด้วยมือได้ว่า 14 วันก่อนเป็นวันพุธ อีกสองวันหลังจากนั้นคือวันศุกร์ จำรูปนี้ไว้ใช้ทุกครั้งที่ค่าอาจติดลบ

((x % m) + m) % m    ได้ค่าระหว่าง 0 ถึง m - 1 เสมอ

ทำไมโจทย์ให้ตอบ mod 1000000007

ห้องหนึ่งมีนักเรียน N คน ครูจะเลือกกลุ่มหนึ่งไปแข่งขัน จะเลือกกี่คนก็ได้ นักเรียนแต่ละคนมีสองทาง ไปหรือไม่ไป จำนวนแบบทั้งหมดจึงเป็น 2 × 2 × ... × 2 = 2^N แบบ ถ้า N = 100 คำตอบคือ 1267650600228229401496703205376 ยาว 31 หลัก ส่วน long long เก็บได้แค่ 19 หลัก

โจทย์นับจำนวนวิธีแทบทุกข้อเจอปัญหานี้ คนตั้งโจทย์จึงสั่งว่า "ตอบเป็นเศษจากการหารด้วย 1000000007" (ก็คือ 10⁹ + 7 ซึ่งโจทย์มักเขียนแบบนี้) ตัวเลขนี้ถูกเลือกเพราะ

• ค่าที่ mod แล้วอยู่ระหว่าง 0 ถึง 1000000006 เก็บใน int ได้
• สองค่านั้นบวกกัน ได้ไม่เกิน 2000000012 ยังไม่เกิน int ที่เก็บได้ถึง 2147483647
• สองค่านั้นคูณกัน ได้ไม่เกินราว 10¹⁸ ยังไม่เกิน long long ที่เก็บได้ราว 9.2 × 10¹⁸
• เป็นจำนวนเฉพาะ ซึ่งมีประโยชน์กับเทคนิคขั้นสูงที่อยู่นอกหลักสูตรนี้ ตอนนี้ไม่ต้องใช้

บางโจทย์ใช้ 998244353 แทน ทุกอย่างในหน้านี้ใช้ได้เหมือนกัน

ตั้งชื่อให้ค่าคงที่ด้วย #define

เลข 1000000007 จะโผล่หลายที่ในโปรแกรม พิมพ์ผิดศูนย์เดียวก็ได้คำตอบผิดทั้งข้อ จึงตั้งชื่อให้มันครั้งเดียวที่บรรทัดบนสุด

#define MOD 1000000007

#define สั่งให้ compiler เอา 1000000007 ไปแทนคำว่า MOD ทุกที่ก่อนคอมไพล์ ไม่มีเครื่องหมาย = และไม่มี ; ท้ายบรรทัด ชื่อแบบนี้นิยมเขียนเป็นตัวพิมพ์ใหญ่ทั้งหมด จะได้รู้ว่าเป็นค่าคงที่ ไม่ใช่ตัวแปร

บวก ลบ คูณ แบบ mod

ความลับที่ทำให้ไม่ต้องเก็บเลข 31 หลักคือ ถ้าสุดท้ายต้องการแค่เศษ ระหว่างทางก็เก็บแค่เศษได้ เหมือนเข็มสั้นของนาฬิกา เดินไปกี่ชั่วโมงก็ตาม สิ่งที่บอกตำแหน่งเข็มคือจำนวนชั่วโมงหารด้วย 12 เหลือเศษเท่าไร ไม่ต้องจำว่าเดินมาแล้วกี่รอบ เขียนเป็นกฎได้แบบนี้ เมื่อ m คือ 1000000007

(a + b) % m  ==  ((a % m) + (b % m)) % m
(a * b) % m  ==  ((a % m) * (b % m)) % m
(a - b) % m  ==  ((a % m) - (b % m) + m) % m

ในโค้ดแปลว่า mod ทันทีหลังบวกหรือคูณทุกครั้ง ค่าในตัวแปรจะอยู่ระหว่าง 0 ถึง m - 1 ตลอดเวลา ผลคูณของสองค่าแบบนี้ไม่เกิน 10¹⁸ เก็บใน long long ได้เสมอ นับแบบเลือกนักเรียนไปแข่งได้แบบนี้

#include <stdio.h>
#define MOD 1000000007

int main()
{
    int n;
    scanf("%d", &n);
    long long ways = 1;
    for (int i = 0; i < n; i++) {
        ways = ways * 2 % MOD;
    }
    printf("%lld\n", ways);
    return 0;
}

100

976371285

ways * 2 % MOD ทำจากซ้ายไปขวา คูณก่อนแล้วค่อย mod ตามลำดับการคำนวณในหน้า 1.2 แฟกทอเรียลที่ล้น long long ตั้งแต่ 21! ในหน้า 4.2 ก็คิดแบบเดียวกัน

#include <stdio.h>
#define MOD 1000000007

int main()
{
    int n;
    scanf("%d", &n);
    long long answer = 1;
    for (int i = 1; i <= n; i++) {
        answer = answer * i % MOD;
    }
    printf("%lld\n", answer);
    return 0;
}

100

437918130

ลบแล้วต้องบวก MOD กลับ

รหัสผ่านยาว N หลัก แต่ละหลักเป็น 0 1 หรือ 2 ต้องมีเลข 2 อย่างน้อยหนึ่งตัว มีได้กี่แบบ วิธีคิดคือนับทั้งหมด 3^N แบบ แล้วลบแบบที่ไม่มีเลข 2 เลย ซึ่งมี 2^N แบบ

#include <stdio.h>
#define MOD 1000000007

int main()
{
    int n;
    scanf("%d", &n);
    long long all = 1, no_two = 1;
    for (int i = 0; i < n; i++) {
        all = all * 3 % MOD;
        no_two = no_two * 2 % MOD;
    }
    printf("all     = %lld\n", all);
    printf("no two  = %lld\n", no_two);
    printf("wrong   = %lld\n", (all - no_two) % MOD);
    printf("correct = %lld\n", (all - no_two + MOD) % MOD);
    return 0;
}

29

all     = 376884473
no two  = 536870912
wrong   = -159986439
correct = 840013568

ของจริง 3²⁹ มากกว่า 2²⁹ แน่นอน แต่หลัง mod แล้ว เศษของ 3²⁹ บังเอิญน้อยกว่า ลบกันจึงติดลบ เป็นปัญหาเดียวกับวันในสัปดาห์ข้างบน บวก MOD เข้าไปก่อน mod ทำให้ผลกลับมาอยู่ระหว่าง 0 ถึง MOD - 1 เพราะทั้งสองค่าอยู่ระหว่าง 0 ถึง MOD - 1 อยู่แล้ว ผลลบจึงไม่ต่ำกว่า -(MOD - 1) บวก MOD ครั้งเดียวก็พอ ชุดทดสอบเล็กๆ มักไม่ติดลบ โปรแกรมที่ลืมบวก MOD จึงผ่านตัวอย่างแต่ตกชุดใหญ่

ยกกำลังแบบเร็ว

ถ้าโจทย์ถาม A^N mod 1000000007 เมื่อ N ใหญ่ถึง 10¹⁸ ลูปคูณ N รอบแบบโปรแกรม pow2 ไม่มีทางทัน ตามหลักในหน้า 4.5 หนึ่งวินาทีทำได้ราว 10⁸ รอบเท่านั้น

หน้า 9.2 เขียนยกกำลังแบบแบ่งครึ่งไปแล้ว ทบทวนสั้นๆ คือหา A^N/2 ครั้งเดียวแล้วยกกำลังสอง ถ้า N เป็นเลขคี่คูณ A เพิ่มอีกตัว เลขชี้กำลังลดลงครึ่งหนึ่งทุกครั้งที่เรียก สิ่งที่หน้านี้เพิ่มมีสองอย่าง คือ mod ทุกครั้งที่คูณตามกฎในหัวข้อที่แล้ว และเลขชี้กำลังเป็น long long เพราะใหญ่ถึง 10¹⁸

#include <stdio.h>
#define MOD 1000000007

long long power(long long base, long long exp)
{
    if (exp == 0) { // (1)!
        return 1;
    }
    long long half = power(base, exp / 2); // (2)!
    long long result = half * half % MOD;
    if (exp % 2 == 1) {
        result = result * base % MOD;
    }
    return result;
}

int main()
{
    long long base, exp;
    scanf("%lld %lld", &base, &exp);
    printf("%lld\n", power(base % MOD, exp)); // (3)!
    return 0;
}

1. กรณีฐานของ recursion ทุกอย่างยกกำลัง 0 ได้ 1
2. เรียกตัวเองครั้งเดียวแล้วใช้ half ซ้ำ เหตุผลเดียวกับแบบที่ 1 ในส่วนลองทำให้พังของหน้า 9.2
3. mod ฐานก่อน ฐานที่รับเข้ามาอาจใหญ่ถึง 10¹⁸ ถ้าไม่ลดก่อน result * base จะล้น long long

2 1000000000000000000

719476260

ไล่การเรียก power(3, 13) ดูว่ามันทำงานอย่างไร (ตัวเลขเล็กจน mod ไม่มีผล)

อ่านจากล่างขึ้นบนคือลำดับการเรียก อ่านจากบนลงล่างคือลำดับที่คำตอบถูกส่งกลับ ทุกครั้งที่เรียก exp ลดลงครึ่งหนึ่ง เลข 10¹⁸ หารสองไปเรื่อยๆ 60 ครั้งก็เหลือ 0 การเรียกจึงลึกแค่ 60 ชั้น แต่ละชั้นคูณไม่เกินสองครั้ง รวมไม่เกิน 120 ครั้ง เทียบกับลูปธรรมดาที่ต้องคูณ 10¹⁸ ครั้ง

เร็วขึ้นแค่ไหน

เพิ่ม clock() แบบหน้า 4.5 ครอบส่วนที่คำนวณของทั้งสองวิธี วิธีลูปคือ

long long result = 1;
for (long long i = 0; i < exp; i++) {
    result = result * base % MOD;
}

วัดบนเครื่องที่เขียนเอกสารนี้ คือโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 ระบบ Windows 11 เสียบสายชาร์จ โหมดพลังงาน Balanced คอมไพล์ด้วย GCC 14.2 ของ Code::Blocks ใช้ฐาน 2 รันแบบละ 5 ครั้ง ตารางเป็นค่ากลางของ 5 ครั้งนั้น

ลูปที่มีทั้งคูณและ mod ใช้เวลาราว 3 วินาทีต่อ 10⁹ รอบ ช้ากว่าลูปที่มีแค่ % ในหน้า 4.5 เกินสองเท่า ถ้าเลขชี้กำลังเป็น 10¹⁸ ลูปจะใช้ราว 3 × 10⁹ วินาที หรือประมาณ 95 ปี ส่วนวิธีเร็วได้ 0.000 ทุกครั้งทั้งสองแบบ คือเร็วเกินกว่าที่ clock() วัดได้ แม้เลขชี้กำลังจะเป็น 10¹⁸

หน้า 12.3 มียกกำลังแบบเร็วอีกแบบที่ใช้ลูปแทน recursion โดยอ่านเลขชี้กำลังเป็นเลขฐานสอง

ลองทำให้พัง

แบบที่ 1 ตรวจเลขคี่ด้วย % 2 == 1

นับว่าในข้อมูลมีเลขคี่กี่ตัว ข้อมูลมี -3 -1 1 3 เป็นเลขคี่ คำตอบที่ถูกคือ 4

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int odd = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        if (x % 2 == 1) {
            odd++;
        }
    }
    printf("odd = %d\n", odd);
    return 0;
}

7
-3 -2 -1 0 1 2 3

odd = 2

-3 % 2 ได้ -1 ไม่ใช่ 1 เลขคี่ที่ติดลบจึงหลุดไปหมด แก้เป็น x % 2 != 0 ซึ่งถูกทั้งเลขบวกและลบ

แบบที่ 2 mod แค่ตอนท้าย

ในโปรแกรม pow2 ย้าย % MOD ออกจากลูปไปไว้ตอนพิมพ์ คิดว่า mod ครั้งเดียวตอนท้ายก็ได้ผลเท่ากัน

#include <stdio.h>
#define MOD 1000000007

int main()
{
    int n;
    scanf("%d", &n);
    long long ways = 1;
    for (int i = 0; i < n; i++) {
        ways = ways * 2;
    }
    printf("%lld\n", ways % MOD);
    return 0;
}

100

0

ได้ 0 แทน 976371285 กฎ mod บอกว่าผลเท่ากันก็จริง แต่ใช้ได้กับค่าจริงเท่านั้น ways ล้นตั้งแต่ 2⁶³ แล้ว ค่าในกล่องจึงไม่ใช่ 2¹⁰⁰ อีกต่อไป ลองป้อน 62 จะได้คำตอบถูก แต่ป้อน 63 ได้เลขติดลบ ถ้าโจทย์บอกให้ตอบ mod แปลว่าคำตอบจริงใหญ่จนเก็บไม่ได้ ต้อง mod ทุกครั้งที่คำนวณ

แบบที่ 3 เก็บค่าที่ mod แล้วใน int

ค่าที่ mod แล้วไม่เกิน 1000000006 เก็บใน int ได้ หลายคนจึงประกาศ answer ในโปรแกรม factorial เป็น int

#include <stdio.h>
#define MOD 1000000007

int main()
{
    int n;
    scanf("%d", &n);
    int answer = 1;
    for (int i = 1; i <= n; i++) {
        answer = answer * i % MOD;
    }
    printf("%d\n", answer);
    return 0;
}

13

932053497

โปรแกรม factorial ที่ใช้ long long ตอบ 227020758 ป้อน 12 ยังถูกทั้งสองแบบ แต่ 13 ผิด เพราะ 12! = 479001600 คูณ 13 ได้ราว 6.2 × 10⁹ ล้น int ไปก่อนจะได้ mod กับดักเดียวกับหน้า 1.3 กล่องที่เก็บค่าเล็กพอ แต่ผลคูณระหว่างทางไม่เล็ก ตัวแปรที่จะเอามาคูณแบบ mod ให้เป็น long long ทุกตัว

สรุป

• ภาษา C หารตัดทศนิยมไปทาง 0 และเศษมีเครื่องหมายตามตัวตั้ง -7 % 3 ได้ -1
• อยากได้เศษแบบคณิตศาสตร์ระหว่าง 0 ถึง m - 1 ใช้ ((x % m) + m) % m ตรวจเลขคี่ใช้ x % 2 != 0
• คำตอบใหญ่เกินให้ตอบ mod 1000000007 ใช้ #define MOD 1000000007 แล้ว mod ทุกครั้งหลังบวกหรือคูณ
• ลบแบบ mod ต้องบวก MOD ก่อน mod ส่วนการหารใช้กฎ mod ไม่ได้
• ตัวแปรที่จะคูณแบบ mod ต้องเป็น long long
• ยกกำลังแบบเร็วลดเลขชี้กำลังลงครึ่งหนึ่งทุกครั้ง 10¹⁸ ใช้แค่ราว 60 ชั้น ส่วนลูปธรรมดาใช้ราว 3 วินาทีต่อ 10⁹ รอบบนเครื่องที่เขียนเอกสารนี้