CSES - Counting Divisors 題解
我把這題想太複雜了…… 弄了個爛解 題目 Time limit: 1.00 s Memory limit: 512 MB Given nnn integers, your task is to report for each integer the number of its divisors. For example, if x=18x=18x=18, the correct answer is 666 because its divisors are 1,2,3,6,9,181,2,3,6,9,181,2,3,6,9,18. Input Output The first input line has an integer nnn: the number of integers. After this, there are nnn lines, each containing an integer xxx. For each integer, print the number of its divisors. Constraints 1≤n≤...
[演算法] 線性篩
埃拉托斯特尼篩法 我們從大家國一就學過的埃拉托斯特尼篩法開始。 維護一個布林陣列not_prime，索引為iii那欄表示數字iii是否為質數，若為質數則該欄為0，若為合數則為1。 我之所以用0表示質數1表示合數是因為如此可省去初始化填入1的步驟。 而埃拉托斯特尼篩法的邏輯就是先預設所有數都是質數，再一步步把不是的劃掉 因為大家都學過這個篩法的步驟和原理(去問你國中數學老師)，以下直接上程式 std::vector<int> prime; bool not_prime[N+1]; void Eratosthenes(int n) { not_prime[0] = not_prime[1] = true; for (int i=2; i<=n; i++) { if (!not_prime[i]) { prime.push_back(i); // 將質數加入 prime if (1LL*i*i > n) continue; for (int j=i*i; j<=n; j+=i) n...
GPN CTF 2026 Writeup
因為考上台大了，這個暑假打算上CTFtime上找一些比賽來打。本來想說畢業當周周末來打這個GPN CTF 2026，結果開賽前突然看到零日餅乾社裡傳一個ISIP-HS CTF，比賽時間包含這個GPN CTF，結果就變成GPN CTF只解了兩三題(還簡單題XD)(都在打ISIP-HS CTF)。 Sanity Check Welcome題，點進Rule看即可 Flag: GPNCTF{Yes Chef! I am ready for a fair competition} Double Fried 題目給了一個pcap檔案，用Wireshark去開 發現訊息有R開頭跟F開頭兩種，而從圖一可以猜出F開頭的是雜訊，所以我們只看R開頭的。 用frame contains "R"進行篩選 然後手動把Flag字母接起來因為我也只會人工接起來 Flag: GPNCTF{NICe, yOu FoUnD 0U7 wHO dID NOt b3L0ng ThEr3} Auto Cooker 把題目給的檔案丟進IDA逆向 int __fastcall main(int a...
CSES Missing Number 題解
題目 我覺得把題目複製過來是最累的一件事 Time limit: 1.00 s Memory limit: 512 MB You are given all numbers between 1,2,…,n1,2,\ldots,n1,2,…,n except one. Your task is to find the missing number. Input Output The first input line contains an integer nnn.The second line contains n−1n-1n−1 numbers. Each number is distinct and between 111 and nnn (inclusive). Print the missing number. Constraints 2≤n≤2⋅1052 \le n \le 2 \cdot 10^52≤n≤2⋅105 Example: Input Output 52 3 1 5 4 解法 解法一 分析 這一個是我的做法 ...
CSES Dice Combinations 題解
DP? 想成高中數學的遞迴就好啦 題目 Time limit: 1.00 s Memory limit: 512 MB Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6. For example, if n=3, there are 4 ways: 1+1+1 1+2 2+1 3 Input Output The only input line has an integer nnn. Print the number of ways modulo 109+710^9+7109+7. Constraints 1≤n≤1061 \le n \le 10^61≤n≤106 Example: Input Output 3 4 解法 分析 這是DP入門題 給定n∈Nn\in\Nn∈N，令dp[n]...
[Note] Writing a simple Program in C - LiveOverflow
看了這部影片 Writing a simple Program in C - YouTube 做的筆記 PATH env | grep "PATH" # or echo $PATH #this one # add to PATH(for one time) export PATH=$PATH:directory vim 基礎 :syntax on #上色 :set number #標號 C 語言 #include <stdio.h> int main(int argc, char *argv[]){ if(argc==2){ printf("Knock, Knock, %s\n", argv[1]); } else { fprintf(stderr, "Usage: %s <name>\n", argv[0]); return 1; } } 解析： argc: 參數數量(從檔案名稱算起) argv: 參數矩陣(包含檔案名稱) 範...
CSES Bracket Sequences I 題解
題目 Time limit: 1.00 s Memory limit: 512 MB Your task is to calculate the number of valid bracket sequences of length nnn. For example, when n=6n=6n=6, there are 555 sequences: ()()() ()(()) (())() ((())) (()()) Input Output The only input line has an integer nnn. Print the number of sequences modulo 109+710^9+7109+7. Constraints 1≤n≤1061 \le n \le 10^61≤n≤106 Example: Input Output 6 5 解法 這題很顯然是在考卡特蘭數 卡特蘭數 定義 卡特蘭數CnC_nCn表示有A, B各nnn個，A永不落後B的排列方法數。組合學上有很多問題都跟卡特蘭數有關。 公式...
CSES Trailing Zeros 題解
題目 Time limit: 1.00 s Memory limit: 512 MB Your task is to calculate the number of trailing zeros in the factorial n!. For example, 20!=243290200817664000020!=243290200817664000020!=2432902008176640000 and it has 444 trailing zeros. Input Output The only input line has an integer nnn. Print the number of trailing zeros in n!n!n!. Constraints 1≤n≤1091 \le n \le 10^91≤n≤109 Example: Input Output 20 4 解法 分析 這題十分經典，是要求n!n!n!尾部有幾個000。 注意到n!n!n!尾部000的個數===滿足10k∣n!10^k | n!10...
CSES Exponentiation II 題解
本題會用到上次在CSES Exponentiation 題解 | R3X’s Blog講到的東西，並假設讀者都已看過。 題目 Time limit: 1.00 s Memory limit: 512 MB Your task is to efficiently calculate values abca^{b^c}abc modulo 109+710^9+7109+7. Note that in this task we assume that 00=10^0=100=1. Input Output The first input line contains an integer nnn: the number of calculations.After this, there are nnn lines, each containing three integers a,ba, ba,b and ccc. Print each value abca^{b^c}abc modulo 109+710^9+7109+7. Constraints 1≤n≤...
CSES Exponentiation 題解
題目 Time limit: 1.00 s Memory limit: 512 MB Your task is to efficiently calculate values aba^bab modulo 109+710^9+7109+7. Note that in this task we assume that 00=10^0=100=1. Input Output The first input line contains an integer nnn: the number of calculations.After this, there are nnn lines, each containing two integers aaa and bbb. Print each value aba^bab modulo 109+710^9+7109+7. Constraints 1≤n≤2⋅1051 \le n \le 2 \cdot 10^51≤n≤2⋅105 0≤a,b≤1090 \le a,b \le 10^90≤a,b≤109 Exampl...