Statement

สรุปคำถามสำหรับข้อนี้คือ ให้เลขมา $10$ เลข จากนั้นนำเลขแต่ละตัวมาหารเอาเศษด้วย $42$ แล้วถามว่า หลังจากหารเอาเศษแล้ว มีจำนวนเลขที่แตกต่างกันกี่เลข

Solution

วิธีทำข้อนี้คือลองสังเกตจากคุณสมบัติการหารเอาเศษก่อน กล่าวคือกำหนดให้ $N$ เป็นจำนวนเต็มใด ๆ (ลบ ศูนย์ บวก) เมื่อนำเลข $N$ มาหารเอาเศษด้วย $M$(เขียนด้วยโค้ด N % M คือผลจากการนำ $N$ มาหารเอาเศษด้วย $M$ หรือเขียนให้ทางการหน่อยก็ $N \mod M$) สุดท้ายแล้วจะได้ว่าผลลัพธ์จากการหารเอาเศษมีได้แค่ $M$ แบบที่แตกต่างกันเท่านั้นคือ $0, 1, 2, ..., M-1$

ตัวอย่างเช่น ให้ $M = 3$ จะได้ว่าเมื่อเรานำจำนวนเต็ม $N$ อะไรมาก็ตามหารเอาเศษด้วย $M$ จะได้ว่า N % 3 ผลลัพธ์จะมีแค่ $0, 1, 2$ เท่านั้น เช่นลองไล่เลขมาดังนี้ $0 \mod 3 = 0, \newline 1 \mod 3 = 1, \newline 2 \mod 3 = 2, \newline 3 \mod 3 = 0, \newline 4 \mod 3 = 1, \newline 5 \mod 3 = 2, \newline 6 \mod 3 = 0, \newline ...$ ทุกผลลัพธ์มันจะเริ่มวนย้อนกลับมาอยู๋ในเลข $0, 1, ..., M-1$ แล้วนั่นเอง

จากข้อสังเกตนี้ เราสามารถนำมาปรับใช้กับเลข $42$ ได้นั่นคือให้ $M = 42$ จะได้ว่าผลลัพธ์จากการหารเอาเศษด้วย $42$ มีได้แค่เพียง $0, 1, 2, ..., 41$

จากตรงนี้เราสามารถสร้าง array ชื่อ $cnt$(ย่อมาจาก count ที่แปลว่านับ) มาเก็บข้อมูลการปรากฎของเลขที่ได้จากผลลัพธ์เหล่านี้ได้ ก็จะได้ array $cnt$ มีทั้งหมด $42$ ช่องข้อมูล(มี $index$ ตั้งแต่ $0$ ถึง $41$) จากนั้นกำหนดให้ทุกช่องมีค่าเป็น $0$ ซึ่งหมายถึงว่ายังไม่มีเลขใด(ในช่วง $0$ ถึง $41$)ปรากฎเลย

ทีนี้หากเรานำจำนวนเต็มสักตัวมา สมมติชื่อ $num$ เราก็นำจำนวนเต็มนั้นไปหารเอาเศษด้วย $42$ จะได้ว่าผลลัพธ์มันจะเป็น $index$ สักตัวของ $cnt$ แน่ ๆ (มาจากข้อสังเกตการหารเอาเศษ) เราก็จะทำการกำหนดค่า(assign) ให้ $cnt$ ช่อง $index$ นั้นเป็น $1$ เพื่อบอกว่ามีเลขนี้(num%42)ปรากฎขึ้นในผลลัพธ์ที่แตกต่างใด ๆ แล้ว(เพราะตอนแรกเป็น $0$ ซึ่งหมายถึงยังไม่มีเลขนี้ปรากฏ)

เมื่อเรามีข้อมูลการปรากฎของเลขต่าง ๆ แล้ว คำตอบของโจทย์ข้อนี้ก็คือว่า นับไปทีละเลขตั้งแต่ $0, 1, 2, ..., i, ..., 41$ แล้วดูว่าเลขไหนบ้างที่ค่าของ $cnt$ ในช่องที่ $i$ เป็น $1$ (ซึ่งหมายถึงว่าเลข $i$ ได้ปรากฎแล้ว) ก็บวก $1$ เพิ่มเข้าไปในค่าคำตอบ ($ans$) เพียงเท่านี้ก็จบแล้ว

Code

#include <stdio.h>

int main()
{
    int cnt[42] = {}; // สร้างมา 42 ช่องทุกช่องเป็น 0
    for (int i = 0; i < 10; i++) {
        int num;
        scanf("%d", &num);
        int index = num % 42; 
        cnt[index] = 1;
    }

    int ans = 0;
    for (int i = 0; i < 42; i++) {
        if (cnt[i] == 1) {
            ans += 1;
        }
    }

    printf("%d", ans);
    return 0;
}