Solost - 数学
type: channel
link: https://solost.cn/tag/%E6%95%B0%E5%AD%A6/
items: AcWing 867. 分解质因数
items: AcWing 869. 试除法求约数
items: Codeforces Round 883 (Div. 3) - E2. Rudolf and Snowflakes (hard version)
items: Codeforces Round 878 (Div. 3) - B. Binary Cafe
items: Codeforces Round 871 (Div. 4) - G. Hits Different
items: AtCoder Beginner Contest 290 - D - Marking
items: 2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

AcWing 867. 分解质因数
type: item
date: 2023-09-12T11:30:48+08:00
description: 题目链接链接代码#include <iostream> #include <algorithm> using namespace std; void divide(int x) { for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ' ' << s << endl; } if (x > 1) cout << x << ' ' << 1 << endl; cout << endl; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; divide(x); } return 0; }

AcWing 869. 试除法求约数
type: item
date: 2023-09-12T11:29:33+08:00
description: 题目链接题目链接代码#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> get_divisors(int x) { vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i); } sort(res.begin(), res.end()); return res; } int main() { int n; cin >> n; while (n -- ) { int x; cin >> x; auto res = get_divisors(x); for (auto x : res) cout << x << ' '; cout << endl; } return 0; }

Codeforces Round 883 (Div. 3) - E2. Rudolf and Snowflakes (hard version)
type: item
date: 2023-07-08T15:20:29+08:00
description: 题目链接链接题目大意问有没有生成的雪花节点数等于n?雪花是刚开始是一个点，后面从一个点连接K个节点，再从k个节点再连接K个点，easy版本是n<=1e6,hard version是n<=1e18题解easy版本暴力即可，直接预处理出所有的情况，刚开始雪花节点数目是，1 + k + k ^2，然后每次加K^i，hard version不能这样写，因为时间复杂度太高了，所以我们使用二分搜索，int是2^32，约为10位，long long 64位，约长18位，__int 128 128位。所以计算pow(k, i)不能直接算，会溢出，所以边乘边算。代码#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2e5 + 10; const ll P = 1e9, K = 2e18; ll check(ll k, ll cnt) { __int128 s = 1, pr = 1; for (ll i = 1; i <= cnt; i++) { pr = pr * k; s += pr; if (s >= K) return K; } ll res = s; return res; } void solve() { ll n; cin >> n; for (ll i = 2; i <= 62; i++) { ll l = 2, r = P; while (l < r) { ll mid = (l + r) / 2; ll x = check(mid, i); if (x == n) { cout << "YES\n"; return; } else if (x > n) r = mid; else l = mid + 1; } } cout << "NO\n"; } int main() { IOS; int _ = 1; cin >> _; while (_--) { solve(); } return 0; }

Codeforces Round 878 (Div. 3) - B. Binary Cafe
type: item
date: 2023-07-06T15:56:29+08:00
description: 题目链接链接题目大意有 k 种商品，编号为 0 至 k−1，编号为 i 的商品的价格为2^i，问你在花的钱数不超过 n 且每种商品最多买一个（可以不买所有商品）的前提下，有多少种购买商品的方式。某个商品只有两种情况，买还是不买，这就像二进制，从右往左，第i个位0代表不买，否则买，问K位以内，能有多少个二进制转换为10进制小于等于n。如果有k位，那么可以表示[0, 2^k - 1]的数字都可以表示出来，因为2进制表示是唯一的，例如8 = 2^3,再没有其他的表示办法， 所以不能被其他替代，所以，[0, 2^k - 1]的数字都有唯一的二进制表示方法，如果n <= 2^k -1,那么最多表示[0, n]一共n+1个数字，如果小于的话可以表示[0, 2^k - 1]范围内的数，一共2^k个。又因为1<<30就会爆int,超过1e9，特判即可#include #include <set> #include <cmath> #include <queue> #include <stack> #include <vector> #include <bitset> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <algorithm> #include <unordered_map> #include <unordered_set> #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2e5 + 10; void solve() { int n, k; cin >> n >> k; if(k >= 30 || n <= pow(2, k) - 1){ cout << (n + 1) << endl; } else{ cout << (1 << k) << endl; } } int main() { IOS; int t = 1; cin >> t; while (t--) { solve(); } return 0; }

Codeforces Round 871 (Div. 4) - G. Hits Different
type: item
date: 2023-05-11T20:46:49+08:00
description: 题目链接题目链接题目大意给你一个2023行的杨辉三角，然后按照从左到右从上到下的顺序标号，每个序号的方块值等于自己序号的平方，问你打掉某个序号的方块，所有掉落方块的值的和是多少？打掉一个方块，该方块连接的也会掉（上一层）打掉9会掉5，6。题解大概就是2023*2023/2的时间复杂度。首先按照杨辉三角的样子生成杨辉三角，并算出每个方块的值。首先打掉例如说9这个方块掉的值不是5所有掉的和6所有掉落的，那是因为5和6有重复的地方，所以不能直接那么计算，通过观察找规律发现，每个方块打掉一共掉落的数目是该列斜对角线的所有块。然后使用前缀和计算即可。例如说打8吧，第一个斜对角就是4，8前一行是2，5再前一行就是1，3。所以每个方块掉落值就是斜对角线所有的和。代码#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2040; ll a[N][N], b[N][N], d[N][N]; map<ll, pll> q; void solve() { ll cnt = 1, c = 1; for (int i = 1; i <= 2023; i++) { int j = 1; while (j <= i) { a[i][j] = cnt * cnt; q[cnt] = { i, j }; cnt++; j++; } } d[1][1] = a[1][1]; for(int i = 2; i <= 2023; i++){ for(int j = 1; j <= i; j++){ d[i][j] = d[i - 1][j - 1] + a[i][j];//计算每个方块斜对角线的方块值的和 } } // cout << "--------------------\n"; for(int i = 1; i <= 2023; i++){ for(int j = 1; j <= i; j++){ d[i][j] += d[i - 1][j];//然后求当前斜对角线上面的所有的和 } } } int main() { IOS; int t = 1; solve(); cin >> t; while (t--) { int x; cin >> x; cout << d[q[x].x][q[x].y] << endl; } return 0; }

AtCoder Beginner Contest 290 - D - Marking
type: item
date: 2023-03-18T20:17:00+08:00
description: 题目链接[](https://atcoder.jp/contests/abc290/tasks/abc290_d)solution题目大意是给你一个n, d, k，从0开始，每次增加d，如果超出n就mod n，如果这个点已经经过过，那么就+1。我们可以手写几个样例，发现每个回合有g = n / gcd(n, d)个，那么我们只需定位他在第几回合和某回合的第几个。那么第k个即d * (k % g) % n + k / g#include #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<bitset> #include<cstdio> #include<cstring> #include<fstream> #include<cstdlib> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; #define x first #define y second #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, mod = 1000000007; const int N = 2e5 + 10; void solve(){ ll n, d, k; cin >> n >> d >> k; k--; ll g = n / __gcd(n, d); ll ans = d * (k % g) % n + k / g; cout << ans << endl; } int main(){ // IOS; int t = 1; cin >> t; while(t--){ solve(); } return 0; }

2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers
type: item
date: 2023-01-19T14:40:00+08:00
description: 2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integerssolution我们先来分析一下，我们需要寻找三个数，然后满足一定的条件，由于n=5000,n的三次方的复杂度肯定是不可取的，我们就得想办法优化常数。1.第一次的错误尝试，使用vector<pair<int, pair<int, int>>>，第一维度存放a[i] a[j] % mod，第二维度存放i,j,然后再枚举a[i]，用f[(a[i] a[j] % mod + a[i] % mod) % mod]++,来存放5000以内的i等于时的答案，最后再将f[i]减去（a[i] a[j] + a[i]和a[i] a[j] + a[j])这种情况。我们可以看出，这个方法基本和暴力没啥区别，属于脱裤子放屁了。2.第二次尝试，我们换个思路，aiaj没办法压缩（ps.刚开始没想到压缩这个），我们就压缩a[i],我们将a[i] % mod，存放到b[i]里面，计算a[i] % mod后相同的数目，最后再将(a[i] a[j] % mod + i % mod) % mod的数目计算出来就可以了，再减去a[i] a[j] + a[i]和a[i] a[j] + a[j])这种情况。这种情况优化了一部分，但是优化程度还是不够，如果a[i] % mod，但是mod ==5000 == n那就相当于没有优化。于是我们将矛头转向优化a[i] a[j]3.于是有了解法三，我们将b[a[i] * a[j] % mod]的数目先算出来，然后枚举f[a[i] % mod + j % mod]，i属于1-n，j属于0-p -1，这样我们就可以得到答案了。show code#include #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<bitset> #include<cstdio> #include<cstring> #include<fstream> #include<cstdlib> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; #define endl '\n' #define IOS \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; const int INF = 0x3f3f3f3f; const int N = 2e5 + 10; ll a[N], f[5100], b[5100];//由于b里面存储的是次数，因此有可能会爆int，所以顺便存成ll void solve(){ int n, p; cin >> n >> p; int mod = p; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ for(int j = i + 1; j <= n; j++){ b[(1ll * a[i] * a[j]) % mod]++; ll t1 = ((1ll * a[i] * a[j]) % mod + a[i] % mod) % mod; ll t2 = ((1ll * a[i] * a[j]) % mod + a[j] % mod) % mod;//减去有两个数相同的情况 f[t1]--; f[t2]--; } } for(int i = 1; i <= n; i++){ for(int j = 0; j < p; j++){ int t = (a[i] % mod + j % mod) % mod; f[t] += b[j]; } } for(int i = 0; i < p; i++){ cout << f[i] * 2 << " ";//因为三元组前两个数交换无所谓，所以×2，我们计算的时候不会算i,j和j,i只会算一遍 } cout << endl; } int main(){ // IOS; int t = 1; // cin >> t; while(t--){ solve(); } return 0; }