最後更新日期 2024 / 01 / 01

題解 CSES Sum of Divisors

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

題意

定義 σ(x)x 的所有因數之和
給予一個 nk=1nσ(k) 之值

想法

12 為例
先看一下這張圖列出了 112 的所有因數

可以發現每兩個數字就會出現一次 2
每三次數字就會出現一次 3
觀察後可知
對於一個數字 x 它的出現次數會是 nx
因為每 x 個數字就會出現一個 x 的倍數
用這個做法枚舉每個數字計算就可以得到一個 O(n) 的算法
但這樣還不夠快到足以處理這題 1012 的資料量

如果我們把剛剛那張圖的呈現方式改一下
上面那一橫排代表因數 112
下面那一行排代表該因數出現的次數

可以發現這張圖內有幾串連續的因數出現次數相同
因為事實上在計算這個的過程中只會出現最多 2n 個相異數字 (證明)

上面那張圖每個紅色圈起來代表一塊
如果我們可以塊為單位來計算就可以把時間複雜度降到 O(n)

想像一下
如果 n 除以 x 可以剛好整除的話
k=nxnk 必定等於 k
那如果不是剛好整除的呢?
125=2,122=6
再試試看 6
126=2,122=6
觀察後發現
這裡的 6 就是最大的 x 滿足 nx2
於是這樣我們就可以找到最後一個連續出現次數相同的因數
最後只要把每次一塊的第一個數和最後一個數用梯形公式求總和乘上共同的出現次數就可以得到答案了

不過這邊要注意的是
因為答案很大所以題目要我們對 109+7 取模
但梯形公式中又會用到除法
所以我們不能直接除
需要先求出模反元素再乘進去才行

程式碼

#include<bits/stdc++.h>
#define int long long
using 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 Common Divisors

找到兩個數字 使得兩數的最大公因數盡量大可以把題目想成 找到最大的 x 使得陣列中出現至少兩個他的倍數 於是我們可以先用 cnt 陣列紀錄每個數字的出現次數 然後枚舉每個可能的因數 假設目前枚舉到 k 從 k、2k、3k dots 計算陣列中存在多少個倍數 根據調和級數.harmonic-series可以算出時間複雜度為 On log ncppconst int maxn = 1e6 + 10;int cntmaxn;signed main { int n; cin n; vectorint vn; for int i = 0; i n; i++ { cin vi; cntvi++; } for int k = maxn; k 0; k-- { int cur = 0; for int j = k; j maxn; j += k { cur += cntj; } if cur = 2 { cout k endl; return 0; } }}

CSES

題解 CSES Missing Number

給予一堆數字 1 sim n 但中間缺少了一個 你的任務是找出那個缺少的數字已知數字 1 sim n 的總和為 sum^n{k=1}k 可以透過梯形公式 frac{n1 + n}{2} 快速求出來 所以我們只要用期望的 1 sim n 總和減掉輸入的所有數字就可以算出答案了cppusing namespace std; main { iosbase::syncwithstdiofalse;cin.tie0; int n, sum = 0; cin n; for int i = 0; i n-1; i++ { int tmp; cin tmp; sum += tmp; } cout 1 + n n 2 - sum 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