最後更新日期 2024 / 01 / 01

題解 CSES Common Divisors

https://cses.fi/problemset/task/1081/

題意

找到兩個數字
使得兩數的最大公因數盡量大

想法

可以把題目想成
找到最大的 x 使得陣列中出現至少兩個他的倍數
於是我們可以先用 cnt 陣列紀錄每個數字的出現次數
然後枚舉每個可能的因數 (假設目前枚舉到 k)
k2k3k 計算陣列中存在多少個倍數
根據調和級數可以算出時間複雜度為 O(nlogn)

實作

#include <bits/stdc++.h>
#define int long long

const int maxn = 1e6 + 10;
int cnt[maxn];

signed main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        cnt[v[i]]++;
    }
    for (int k = maxn; k > 0; k--) {
        int cur = 0;
        for (int j = k; j < maxn; j += k) {
            cur += cnt[j];
        }
        if (cur >= 2) {
            cout << k << endl;
            return 0;
        }
    }
}

推薦文章

題解 CSES Sum of Divisors

定義 sigmax 為 x 的所有因數之和 給予一個 n 求 sum^n{k=1}sigmak 之值以 12 為例 先看一下這張圖列出了 1 sim 12 的所有因數可以發現每兩個數字就會出現一次 2 每三次數字就會出現一次 3 觀察後可知 對於一個數字 x 它的出現次數會是 lfloor frac{n}{x} rfloor 因為每 x 個數字就會出現一個 x 的倍數 用這個做法枚舉每個數字計算就可以得到一個 On 的算法 但這樣還不夠快到足以處理這題 10^{12} 的資料量如果我們把剛剛那張圖的呈現方式改一下 上面那一橫排代表因數 1 sim 12 下面那一行排代表該因數出現的次數可以發現這張圖內有幾串連續的因數出現次數相同 因為事實上在計算這個的過程中只會出現最多 2 sqrt n 個相異數字 證明上面那張圖每個紅色圈起來代表一塊 如果我們可以塊為單位來計算就可以把時間複雜度降到 Osqrt{n} 了想像一下 如果 n 除以 x 可以剛好整除的話 令 k = lfloor frac{n}{x} rfloor 則 lfloor frac{n}{k} rfloor 必定等於 k 那如果不是剛好整除的呢? lfloor frac{12}{5} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 再試試看 6 lfloor frac{12}{6} rfloor = 2 ,quadlfloor frac{12}{2} rfloor = 6 觀察後發現 這裡的 6 就是最大的 x 滿足 frac{n}{x} 為 2 於是這樣我們就可以找到最後一個連續出現次數相同的因數 最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了不過這邊要注意的是 因為答案很大所以題目要我們對 10^9 + 7 取模 但梯形公式中又會用到除法 所以我們不能直接除 需要先求出模反元素.modulo-inverse再乘進去才行cppusing namespace std;const int mod = 1e9 + 7;const int inv = 500000004; signed main { int n; cin n; int cur = 1; int ans = 0; while cur = n { int cnt = n cur; int last = n cnt; int sum = last + cur % mod last - cur + 1 % mod % mod inv % mod; ans += sum % mod cnt % mod % mod; cur = last + 1; } cout ans % mod endl;}

CSES

題解 CSES Trailing Zeros

n 階乘求數字有幾個後綴 0不難發現 後綴幾個 0 就等於乘進去的 10 的個數 而 10 = 5 times 2 所以後綴 0 數量就相當於計算把每個數質因數分解後 5 和 2 的較少的那個的個數 那當然 5 一定會比 2 少 所以我們要做的是就是計算 5 的個數 那要如何計算呢? 以 30 為例 我們知道要求得 30 階就是要把下面這些數字乘起來 不過我們可以先排除掉質因數分解後裡面沒有 5 的數字 然後把下面的數字都各取走一個質因數分解裡面的 5(相當於除與 5) 並把答案加上 6 因為下面有 6 個數字 變成這樣 可以看到下面的數字剛好就是 6 階乘的子問題 像剛剛的作法一樣 把跟 5 無關的數字排除並把它取走一個 5 的質因數 答案 += 1這樣就完成 30 階的計算了! 根據上面的操作 可以推出下列遞迴式 fx = flfloor frac nx rfloor + lfloor frac nx rfloor不過寫成程式其實用 while 迴圈就可以了 cppusing namespace std;signed main { int n; cin n; if n % 2 { cout 0 endl; return 0; } int ans = 0; while n = 5 { n = 5; ans += n; } cout ans endl;}

CSES

題解 CSES Permutations

給予一個數字 n 你要使用數字 1 sim n 構造一個陣列 使得不存在任意兩個相鄰數字的差為 1把 n 個數字分成 1 sim lfloor frac{n}{2} rfloor 和 lfloor frac{n}{2}+1 rfloor sim n 兩堆 並穿插構造 ans 陣列就可以保證任兩數的差大約為 lfloorfrac{n}{2}rfloor 最後跑過整個陣列驗證是否合法即可cppusing namespace std;signed main { iosbase::syncwithstdiofalse;cin.tie0; int n; cin n; vectorint arrn; dequeint ans; int mid = n2; for int i = 1; i = n2; i ++ { int leftVal = i; int rightVal = mid + i; ans.pushbackrightVal; ans.pushbackleftVal; } if n 1 == 1 { ans.pushfrontmid + n2 +1; } for int i = 0; i n-1; i++ { if absansi+1 - ansi == 1 { cout "NO SOLUTION" endl; return 0 ; } } for int i = 0; i n; i ++ { cout ansi " "; } cout endl;}

CSES