树上问题练习
树的dfs
std::vector<int> tree[100002];
int father[1000002];
int distance[1000002];
int max_distance[1000002];
bool visited[1000002] = {false};
void dfs(int cur_v, int depth) {
visited[cur_v] = true;
max_distance[cur_v] = distance[cur_v] = depth;
for (auto &i : tree[cur_v]) {
if (!visited[i]) {
father[i] = cur_v;
dfs(i, depth + 1);
max_distance[cur_v] = std::max(max_distance[cur_v], max_distance[i]);
}
}
}
father[n] = 0;
dfs(n, 0);
数据结构练习
线段树练习
区间更新（加法）、区间查询（最值）线段树
//
// Created by jiang on 2020/8/12.
// 银川区域赛G
#include <cstdio>
#include <cstring>
#include <array>
long long seq[100008];
std::array<int, 4> seg_tree[400008]; // 本题build初始化
std::array<int, 4> multi_tags[400008];
/**
* 下推懒惰标记
* @param l 左区间端点
* @param r 右区间端点
* @param num 序号
*/
void push_down(int l, int r, int num) {
for (int i = 0; i < 4; ++i)
if (multi_tags[num][i]) {
seg_tree[num << 1][i] += multi_tags[num][i];
seg_tree[num << 1 | 1][i] += multi_tags[num][i];
multi_tags[num << 1][i] += multi_tags[num][i];
multi_tags[num << 1 | 1][i] += multi_tags[num][i];
multi_tags[num][i] = 0;
}
}
/**
* 区间更新
* @param update_l 更新区间左端点
* @param update_r 更新区间右端点
* @param value 更新的值
* @param l 当前搜索区间左端点
* @param r 当前搜索区间右端点
* @param num 线段树序号
*/
void update(int update_l, int update_r, long long value, int l, int r, int num) {
#define ADD(n, v) (multi_tags[num][n] += v, seg_tree[num][n] += v)
if (update_l <= l && r <= update_r) {
if (value == 2) ADD(0, 1);
else if (value == 3) ADD(1, 1);
else if (value == 4) ADD(0, 2);
else if (value == 5) ADD(2, 1);
else if (value == 6) {
ADD(0, 1);
ADD(1, 1);
} else if (value == 7) ADD(3, 1);
else if (value == 8) ADD(0, 3);
else if (value == 9) ADD(1, 2);
else if (value == 10) {
ADD(0, 1);
ADD(2, 1);
}
return;
}
push_down(l, r, num);
int mid = (l + r) / 2;
if (update_l <= mid) {
update(update_l, update_r, value, l, mid, num << 1);
}
if (mid + 1 <= update_r) {
update(update_l, update_r, value, mid + 1, r, num << 1 | 1);
}
for (int i = 0; i < 4; ++i)
seg_tree[num][i] = std::max(seg_tree[num << 1][i], seg_tree[num << 1 | 1][i]);
}
/**
* 区间查询
* @param query_l 查询区间左端点
* @param query_r 查询区间右端点
* @param l 当前搜索区间左端点
* @param r 当前搜索区间右端点
* @param num 线段树序号
* @return 区间查询结果（求区间和）
*/
long long query(int query_l, int query_r, int l, int r, int num) {
if (query_l <= l && r <= query_r) {
int max_value = 0;
for (auto &i : seg_tree[num]) {
max_value = std::max(max_value, i);
}
return max_value;
}
push_down(l, r, num);
long long result = 0;
int mid = (l + r) / 2;
if (query_l <= mid) {
result = std::max(result, query(query_l, query_r, l, mid, num << 1));
}
if (mid + 1 <= query_r) {
result = std::max(result, query(query_l, query_r, mid + 1, r, num << 1 | 1));
}
return result;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
memset(seq, 1, sizeof(seq));
char op[10];
int n1, n2, n3;
for (int i = 0; i < q; ++i) {
scanf("%s %d %d", op, &n1, &n2);
if (op[1] == 'U') {
scanf("%d", &n3);
update(n1, n2, n3, 1, n, 1);
} else {
printf("ANSWER %lld\n", query(n1, n2, 1, n, 1));
}
}
return 0;
}
数论练习
素数筛
luogup1835 求【L， R】间的素数个数
//
// Created by jiang on 2020/8/16.
//
#include <cstdio>
#include <bitset>
#include <vector>
std::bitset<46342> is_prime;
std::bitset<1000001> is_comp;
std::vector<long long> primes;
void thieve() {
is_prime.flip();
for (int i = 2; i <= 46341; ++i) {
if (is_prime[i]) {
primes.push_back(i);
for (int j = i; j <= 46341; j += i) {
is_prime[j] = false;
}
}
}
}
int main() {
thieve();
long long l, r;
scanf("%lld %lld", &l, &r);
if (l == 1) l = 2;
for (auto &i : primes) {
if (i * i > r) break;
for (long long j = std::max(i << 1, (l + i - 1) / i * i); j <= r; j += i)
is_comp[j - l] = true;
}
printf("%llu\n", r - l + 1 - is_comp.count());
return 0;
}
GCD、LCM
https://www.luogu.com.cn/problem/P1414
从n个数中取出1、2、3、...、n个数，使其gcd最大。
解：求出每个因数出现的次数，并对每个次数记录最大的因数。
#include <cstdio>
int arr[100009];
int prime_count[1000009] = {0};
int answer[1000009] = {0};
inline int max(int a, int b) {
return a > b ? a : b;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
}
for (int i = 0; i < n; ++i) {
for (int j = 1; j * j <= arr[i]; ++j) {
if (arr[i] % j == 0) {
prime_count[j]++;
answer[prime_count[j]] = max(answer[prime_count[j]], j);
if (j * j < arr[i]) {
prime_count[arr[i] / j]++;
answer[prime_count[arr[i] / j]] = max(answer[prime_count[arr[i] / j]], arr[i] / j);
}
}
}
}
for (int i = 1; i <= n; ++i)
printf("%d\n", answer[i]);
return 0;
}
hdu5656 求n个数所有挑选组合的gcd之和（gcd+dp）
//
// Created by Jiang Yinzuo on 2020/7/17.
//
#include <cstdio>
#include <algorithm>
#include <cstring>
const int MOD = 100000007;
long long dp[1001][1001];
int arr[1001];
int gcd[1001][1001] = {0};
void get_gcd(int n, int m) {
for (int i = 1; i <= 1000; ++i) {
for (int j = 1; j <= 1000; ++j) {
if (!gcd[i][j]) {
for (int k = 1; k * i <= n && k * j <= m; ++k) {
gcd[k * i][k * j] = k;
}
}
}
}
}
void solve(int n, int max_gcd) {
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; ++i) {
dp[i][arr[i]] = 1;
for (int j = 1; j <= max_gcd; ++j) {
dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
dp[i][gcd[arr[i]][j]] = (dp[i][gcd[arr[i]][j]] + dp[i - 1][j]) % MOD;
}
}
long long answer = 0;
for (int i = 1; i <= max_gcd; ++i) {
answer = (answer + dp[n][i] * i) % MOD;
}
printf("%lld\n", answer);
}
int main() {
get_gcd(1000, 1000);
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
int max_gcd = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", arr + i);
max_gcd = std::max(max_gcd, arr[i]);
}
solve(n, max_gcd);
}
return 0;
}
cf1366D 对正整数a，找到a的大于1的因数b，c使得$$\gcd(b+c,a)=1$$
解：若$$\gcd(b, c) = g > 1$$，则$$b+c和a$$至少有g这个公因数。故仅当存在$$\gcd(b, c) = 1$$时，问题有解。
$$gcd(b, c) = 1 \iff gcd(b+c, c) = 1 \iff gcd(b+c,b) = 1 \iff \gcd(b+c, cb^k) = 1$$。故找到a的最小质因数$$p$$（提前打表），解为$$b = p^k, c = \frac{a}{p^k}, c\bmod b \neq 0 $$
//
// Created by Jiang Yinzuo on 2020/7/23.
//
#include <vector>
#include <cstdio>
int min_prime[10000007] = {0};
void get_min_prime_factor() {
for (int i = 2; i <= 3163; ++i) {
if (min_prime[i] == 0) {
for (int j = i * 2; j <= 10000000; j += i) {
if (min_prime[j] == 0)
min_prime[j] = i;
}
}
}
}
std::vector<int> b_ans, c_ans;
void solve(int a) {
if (min_prime[a] == 0) {
b_ans.push_back(-1);
c_ans.push_back(-1);
return;
}
int c = a;
while (c % min_prime[a] == 0) {
c /= min_prime[a];
}
if (c > 1) {
b_ans.push_back(min_prime[a]);
c_ans.push_back(c);
} else {
b_ans.push_back(-1);
c_ans.push_back(-1);
}
}
int main() {
get_min_prime_factor();
int n;
scanf("%d", &n);
int a;
for (int i = 0; i < n; ++i) {
scanf("%d", &a);
solve(a);
}
for (auto &i : b_ans) {
printf("%d ", i);
}
puts("");
for (auto &i : c_ans) {
printf("%d ", i);
}
puts("");
return 0;
}
因数个数定理
hdu6069：求 $$ (∑\limits_{i=l}^rd(i^k)) \bmod998244353 \space \space \space (1≤l≤r≤10^{12},r−l≤10^6,1≤k≤10^7). $$ $$d(x)$$表示x的因数个数。
显然，1e6以上的质数最多存在一个。故先打表得到1-1e6之间的质数。枚举1-1e6中的每个质数。根据该质数在【l, r】中的出现的次数更新$$d(i^k)$$，并将i /= 质数。质数^2大于r时停止遍历。
//
// Created by Jiang Yinzuo on 2020/7/17.
//
#include <cstdio>
#include <vector>
#include <cstring>
const int MOD = 998244353;
bool is_prime[1000006];
std::vector<int> primes;
void sieve(int n) {
memset(is_prime, true, sizeof(is_prime));
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.push_back(i);
for (int j = i + i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
}
void solve(long long l, long long r, long long k) {
static long long num[1000006];
static long long factor_count[1000006];
for (long long i = l; i <= r; ++i) {
num[i - l] = i;
factor_count[i - l] = 1;
}
for (auto &prime : primes) {
if (prime * prime > r) break;
long long i = (long long) (l / prime) * prime;
while (i < l) i += prime;
for (; i <= r; i += prime) {
long long count = 0;
while (num[i - l] % prime == 0) {
num[i - l] /= prime;
count++;
}
factor_count[i - l] = factor_count[i - l] * (count * k + 1) % MOD;
}
}
long long answer = 0;
for (long long i = l; i <= r; ++i) {
if (num[i - l] == 1)
answer = (answer + factor_count[i - l]) % MOD;
else answer = (answer + factor_count[i - l] * (k + 1) % MOD) % MOD;
}
printf("%lld\n", answer);
}
int main() {
sieve(1000005);
int t;
scanf("%d", &t);
while (t--) {
long long l, r, k;
scanf("%lld %lld %lld", &l, &r, &k);
solve(l, r, k);
}
return 0;
}
南京2018 J
//
// Created by jiang on 2020/9/22.
//
#include <cstdio>
#include <vector>
#include <unordered_map>
constexpr int MAX_N = 1000009;
std::vector<long long> primes;
void euler_thieve() {
static bool not_prime[MAX_N] = {false};
for (int i = 2; i * i < MAX_N; i++) {
if (!not_prime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] < MAX_N; ++j) {
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
std::unordered_map<int, std::vector<long long>> factor_pos;
void factor(int x, int pos) {
// c++11能用for-range循环
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= x; ++i) {
if (x % primes[i] == 0) {
factor_pos[primes[i]].push_back(pos);
do {
x /= primes[i];
} while (x % primes[i] == 0);
}
}
if (x > 1) factor_pos[x].push_back(pos);
}
int main() {
euler_thieve();
int n, a;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a);
factor(a, i);
}
long long ans = 0;
for (auto &i : factor_pos) {
ans += i.second[0] * (n - i.second[0] + 1);
for (int j = 1; j < i.second.size(); ++j) {
ans += (i.second[j] - i.second[j - 1]) * (n - i.second[j] + 1);
}
}
printf("%lld\n", ans);
return 0;
}
CCPC威海2020 D
判断一个数c$$( 1\le c \le 10^{18})$$分解质因数后是否存在相等的质因子。
解：素数筛1e6的质数，c若符合条件，则要么存在两个小于1e6的相等的质因子，要么存在两个大于1e6的相等的质因子、且剩下的质因子都小于1e6。
#include <cstdio>
#include <vector>
#include <cmath>
constexpr int MAX_N = 1000005;
std::vector<long long> primes;
bool not_prime[MAX_N] = {false};
void euler_thieve() {
for (long long i = 2; i < MAX_N; i++) {
if (!not_prime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] < MAX_N; ++j) {
not_prime[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
int main() {
euler_thieve();
int t;
scanf("%d", &t);
while (t--) {
unsigned long long b;
scanf("%llu", &b);
bool yes = false;
for (auto p : primes) {
if (b % p == 0) {
b /= p;
if (b % p == 0) {
yes = true;
break;
}
if (b == 1) {
break;
}
auto _temp = (unsigned long long)sqrt(b);
if (_temp * _temp == b) {
yes = true;
break;
}
}
}
auto _temp = (unsigned long long)sqrt(b);
if (_temp != 1 && _temp * _temp == b) {
yes = true;
}
puts(yes ? "yes" : "no");
}
return 0;
}
pollard_rho
//
// Created by jiang on 2020/8/15.
// 徐州ICPC2019 multiply
#include <cstdio>
#include <ctime>
#include <algorithm>
#include <map>
#define TEST_TIMES 8 // 米勒罗宾素性测试次数
std::map<long long, long long> factor_nums;
/**
* 快速乘法
* @param a
* @param b
* @param p
* @return
*/
long long mul(long long a, long long b, long long p) {
long long ans = 0;
a %= p;
while (b) {
if (b & 1)ans = (ans + a) % p;
b /= 2;
a = (a + a) % p;
}
return ans;
}
/**
* 快速幂取模
* @param a
* @param b
* @param p
* @return
*/
long long pow(long long a, long long b, long long p) {
long long ans = 1;
a %= p;
while (b) {
if (b & 1) ans = mul(a, ans, p);
b /= 2;
a = mul(a, a, p);
}
ans %= p;
return ans;
}
/**
* 米勒罗宾素性测试
* @param n 测试的大数
* @param repeat 测试重复次数
* @return 大概率是素数：true；不是素数：false
*/
bool miller_rabin(long long n, int repeat) {
if (n == 2 || n == 3)return true;//特判
if (n % 2 == 0 || n == 1)return false;//偶数和1
//将n-1分解成2^s*d
long long d = n - 1;
int s = 0;
while (!(d & 1)) ++s, d >>= 1;
//srand((unsigned)time(NULL));在最开始调用即可
for (int i = 0; i < repeat; i++)//重复repeat次
{
long long a = rand() % (n - 3) + 2;//取一个随机数,[2,n-1)
long long x = pow(a, d, n);
long long y = 0;
for (int j = 0; j < s; j++) {
y = mul(x, x, n);
if (y == 1 && x != 1 && x != (n - 1))return false;
x = y;
}
if (y != 1)return false; //费马小定理
}
return true;
}
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
/**
* 找到n的一个因子
* @param n
* @param c
* @return
*/
long long pollard_rho(long long n, long long c) {
long long x = rand() % (n - 2) + 1;
long long y = x, i = 1, k = 2;
for (;;) {
i++;
x = (mul(x, x, n) + c) + n;//不断调整x2
long long d = gcd(y - x, n);
if (1 < d && d < n)
return d;//找到因子
if (y == x)
return n;//找到循环，返回n，重新来
if (i == k) { //一个优化
y = x;
k <<= 1;
}
}
}
void find_factor(long long n, long long c) {
if (n == 1)return;//递归出口
if (miller_rabin(n, TEST_TIMES)) { //如果是素数，就加入
factor_nums[n]++;
return;
}
long long p = n;
while (p >= n)
p = pollard_rho(p, c--);//不断找因子，知道找到为止，返回n说明没找到
find_factor(p, c);
find_factor(n / p, c);
}
long long arr[100005];
/**
* 计算 n!中质因子 x 的数量
* @param n
* @param x
* @return
*/
long long calc(long long n, long long x) {
long long num = 0;
while (n) {
num += n / x;
n = n / x;
}
return num;
}
void solve(int n, long long x, long long y) {
factor_nums.clear();
// c好像也能取2307
find_factor(x, rand() % (n - 1) + 1);
long long ans = 1LL << 61;
for (auto &i : factor_nums) {
long long z_factor_nums = 0;
for (int j = 0; j < n; ++j) {
z_factor_nums += calc(arr[j], i.first);
}
long long y_factor_nums = calc(y, i.first);
ans = std::min(ans, (y_factor_nums - z_factor_nums) / i.second);
}
printf("%lld\n", ans);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n;
long long x, y;
scanf("%d %lld %lld", &n, &x, &y);
for (int i = 0; i < n; ++i) {
scanf("%lld", arr + i);
}
solve(n, x, y);
}
return 0;
}
数学题练习
银川区域赛F
数学题分界通常到$$\sqrt{n}$$，特别是看到$$n = 10^{12}$$
#include <cstdio>
#include <algorithm>
const long long MOD = 998244353LL;
long long calc(long long a, long long n) {
long long ans = 0;
for (long long b = a, t = 1; b <= n; b *= a, ++t) {
ans = (ans + t * (std::min(b * a, n + 1) - b) % MOD) % MOD;
}
return ans;
}
inline long long s1(long long n) {
n %= MOD;
return n * (n + 1) / 2 % MOD;
}
inline long long s2(long long n) {
n %= MOD;
// 6的逆元
return (n % MOD * (n + 1) % MOD * (2 * n + 1) % MOD * 166374059) % MOD;
}
int main() {
long long n;
scanf("%lld", &n);
long long ans = 0, a;
for (a = 2; a * a < n; ++a) {
ans = (ans + a * calc(a, n) % MOD) % MOD;
}
ans = (ans + (n + 1) % MOD * (s1(n) - s1(a - 1) + MOD) % MOD - (s2(n) - s2(a - 1) + MOD) % MOD + MOD) % MOD;
printf("%lld\n", (ans + MOD) % MOD);
return 0;
}
图论练习
拓扑排序
POJ1094
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
const int MAX_VERTEX_NUM = 26;
static int in_deg[MAX_VERTEX_NUM];
static bool graph[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
const int NOT_SORTED = 2;
const int HAS_CIRCLE = 0;
const int SORTED = 1;
/**
* 拓扑排序判断一组字符的顺序。维护in_deg数组，记录每个点的入度。
* 将所有入度为0的点入队，出队时更新以该点为前驱的入度，若有新的点入度为0，则入队。
* 有环：队列为空后，仍然有点未加入结果向量。
* 不能确定排序：过程中队列长度大于1
* 全序：结果向量长度 = 图中点的数量
*/
int topo_sort(int n, std::vector<int> &result) {
std::queue<int> start_q;
int temp_in_deg[MAX_VERTEX_NUM];
for (int i = 0; i < n; ++i) {
if ((temp_in_deg[i] = in_deg[i]) == 0) start_q.push(i);
}
bool not_sorted = false;
while (!start_q.empty()) {
if (start_q.size() > 1) not_sorted = true;
int start = start_q.front();
result.push_back(start);
start_q.pop();
for (int i = 0; i < n; ++i) {
if (graph[start][i])
if (--temp_in_deg[i] == 0) start_q.push(i);
}
}
if (result.size() < n) return HAS_CIRCLE;
return not_sorted ? NOT_SORTED : SORTED;
}
int main() {
int n, m;
char rel[4];
while (scanf("%d %d", &n, &m) && n + m) {
memset(in_deg, 0, sizeof(in_deg));
memset(graph, false, sizeof(graph));
int res;
bool not_end = true;
int edge_id = -1;
std::vector<int> result;
for (int i = 0; i < m; ++i) {
scanf("%s", rel);
if (not_end && !graph[rel[0] - 'A'][rel[2] - 'A']) {
in_deg[rel[2] - 'A']++;
graph[rel[0] - 'A'][rel[2] - 'A'] = true;
result.clear();
res = topo_sort(n, result);
if (res == HAS_CIRCLE || res == SORTED) {
not_end = false;
edge_id = i + 1;
}
}
}
if (res == HAS_CIRCLE) {
printf("Inconsistency found after %d relations.\n", edge_id);
} else if (res == NOT_SORTED) {
printf("Sorted sequence cannot be determined.\n");
} else {
printf("Sorted sequence determined after %d relations: ", edge_id);
for (int i = 0; i < result.size(); ++i) {
printf("%c", result[i] + 'A');
}
printf(".\n");
}
}
return 0;
}
图的BFS
CCPC2019D Path 求有向图第k短的路径
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
struct Edge {
int v;
long long weight;
bool operator<(const Edge &e) const {
return weight < e.weight;
}
};
std::vector<Edge> graph[500009];
struct Path {
int u, v, idx;
long long total_weight;
bool operator>(const struct Path &path) const {
return total_weight > path.total_weight;
}
};
static int max_query = 0;
static long long result[500005];
long long solve(int query, std::priority_queue<Path, std::vector<Path>, std::greater<Path> > &queue) {
Path p{};
while (max_query < query && !queue.empty()) {
p = queue.top();
queue.pop();
result[++max_query] = p.total_weight;
if (0 < p.idx && p.idx < graph[p.u].size()) {
queue.push({p.u,
graph[p.u][p.idx].v,
p.idx + 1,
p.total_weight - graph[p.u][p.idx - 1].weight + graph[p.u][p.idx].weight});
}
if (!graph[p.v].empty()) {
queue.push({p.v, graph[p.v][0].v, 1, p.total_weight + graph[p.v][0].weight});
}
}
return result[query];
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
max_query = 0;
memset(result, 0, sizeof(result));
std::priority_queue<Path, std::vector<Path>, std::greater<Path> > queue;
for (int i = 1; i <= n; ++i) graph[i].clear();
int u, v;
long long w;
for (int i = 0; i < m; ++i) {
scanf("%d %d %lld", &u, &v, &w);
graph[u].push_back({v, w});
queue.push({u, v, -1, w});
}
for (int i = 1; i <= n; ++i) std::sort(graph[i].begin(), graph[i].end());
int query;
for (int i = 0; i < q; ++i) {
scanf("%d", &query);
printf("%lld\n", solve(query, queue));
}
}
return 0;
}