最後更新日期 2024 / 01 / 01
https://cses.fi/problemset/task/1068
給予一個數字
如果他是偶數就把他除
否則就把他乘
重複直到
沒什麼特別的概念
直接模擬操作就可以了
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main() {
int n;
cin >> n;
while(n != 1) {
cout << n << " ";
if (n & 1 == 1) {
n *= 3;
n++;
} else {
n /= 2;
}
}
cout << 1 << endl;
}
找到兩個數字 使得兩數的最大公因數盡量大可以把題目想成 找到最大的 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定義 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給你一個陣列 每次修改可以讓任何一個元素的值加一 最少需要修改幾次才能讓整個陣列變成非嚴格遞增的從陣列左邊往右邊掃過去 遇到凹洞就把它填滿 計算總共需要花多少成本cppusing namespace std;main { iosbase::syncwithstdiofalse;cin.tie0; int n; cin n; int ans = 0; vectorint vecn; for int i = 0; i n; i++ { cin veci; } for int i = 1; i n; i++ { if veci-1 veci { ans += veci-1 - veci; veci = veci-1; } } cout ans;}
CSES