ACM►图论►连通性

HDU1269 - 迷宫城堡(强连通)

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1269

题目大意：

给出一个有向图，判断是否为一个强连通的图。

解题过程：

看完了lrj的白书后去刷的题，裸的板子题，当tarjan练手。

题目分析：

对原图进行强连通分量分解，判断强连通分量的数量是否为1。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

int n, m;

const int MAX = 10000+10;

vector<int> edge[MAX];

//pre表示访问的时间，low是当前节点及其儿子节点能回到的最早的祖先，mark是所在强连通分量的编号
//剩下两个变量是用来计数
int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (!pre[v]) {
            dfs(v);
            //用当前节点的儿子节点更新low数组
            low[u] = min(low[u], low[v]);
        }
        else if (!mark[v]) {
            //用当前节点能回到的祖先节点更新low数组
            low[u] = min(low[u], pre[v]);
        }
    }
    //如果当前节点及其儿子节点都不能返回到更早的祖先节点，那么当前节点就是一个强连通分量的第一次访问到的节点
    if (low[u] == pre[u]) {
        scc_cnt++;
        int x;
        //将当前节点的儿子节点出栈
        do {
            x = S.top(); S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    memset(mark, 0, sizeof(mark));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

int main() {
    while (~scanf("%d %d", &n, &m) && (n + m)) {
        for (int i = 1; i <= n; i++) edge[i].clear();
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            edge[u].push_back(v);
        }
        find_scc(n);
        if (scc_cnt != 1) printf("No\n");
        else printf("Yes\n");
    }
}
ACM►图论►网络流

POJ2195 - Going Home（最小费用流+模板）

题目链接：

http://poj.org/problem?id=2195

题目大意：

给出一张二维的图，每个点距离相邻的点花费为1，图上有相同数量的人和房子，每个房子的容量为1，要使得所有人进入到不同的房子里，最小的花费是多少？

解题过程：

就是裸的最小费用流，建图麻烦点，留下来当模板。
不过这题注意一个坑点是题目描述的数据范围不正确。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <vector>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX = 10012;
const int INF = 0x3f3f3f3f;

struct Info {
    int x, y;
    bool flag;
    Info(int x, int y, bool flag): x(x), y(y), flag(flag) {}
};

struct Edge {
    int u, v, w, cap, nxt;
}edge[MAX<<2];

vector<Info> point;
int head[MAX], tot;
int dist[MAX], vis[MAX], pre[MAX], flow[MAX];

int get_dist(int a, int b) {
    return abs(point[a].x - point[b].x) + abs(point[a].y - point[b].y);
}

void add_edge(int u, int v, int w) {
    edge[tot].u = u;
    edge[tot].v = v;
    edge[tot].cap = 1;
    edge[tot].w = w;
    edge[tot].nxt = head[u];
    head[u] = tot++;

    edge[tot].u = v;
    edge[tot].v = u;
    edge[tot].cap = 0;
    edge[tot].w = -w;
    edge[tot].nxt = head[v];
    head[v] = tot++;
}

void spfa(int s) {
    memset(dist, INF, sizeof(dist));
    queue<int> q;
    q.push(s);
    //flow记录当前节点允许的最大流量
    flow[s] = INF;
    vis[s] = 1;
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            if (edge[i].cap > 0 && dist[v] > dist[u] + edge[i].w) {
                dist[v] = dist[u] + edge[i].w;
                //pre记录当前节点是又那条边过来的
                pre[v] = i;
                flow[v] = min(flow[u], edge[i].cap);
                if (!vis[v]) { q.push(v); vis[v] = 1; }
            }
        }
        vis[u] = 0;
    }
}

int min_cost_flow(int s, int e) {
    int rst = 0;
    while (true) {
        //用spfa求得的最短路增广
        spfa(s);
        //如果和终点无法连通，那么结束
        if (dist[e] == INF) break;
        int d = flow[e], u = e;
        //计算花费
        rst += d * dist[e];
        //更新残量网络
        while (u != s) {
            int last = pre[u];
            edge[last].cap -= d;
            edge[last^1].cap += d;
            u = edge[last].u;
        }
    }
    return rst;
}

int main() {
    int n, m;
    while (~scanf("%d %d", &n, &m) && (n + m)) {
        memset(head, -1, sizeof(head));
        point.clear();
        tot = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char ch;
                scanf(" %c", &ch);
                if (ch == 'H') point.push_back(Info(i, j, true));
                if (ch == 'm') point.push_back(Info(i, j, false));
            }
        }
        int s = point.size();
        int e = s + 1;
        for (int i = 0; i < point.size(); i++) {
            if (!point[i].flag) {
                add_edge(s, i, 0);
                for (int j = 0; j < point.size(); j++) {
                    if (!point[j].flag) continue;
                    add_edge(i, j, get_dist(i, j));
                }
            }
            else add_edge(i, e, 0);
        }
        printf("%d\n", min_cost_flow(s, e));
    }
}
ACM►图论►网络流

HDU4280 - Island Transport（最大流+Dinic模板）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4280

题目大意：

给出$N$个点的坐标和$M$条有容量的边，找出从最西边的点到最东边的点的最大流量。

解题过程：

自己的 Dinic 板子一直 TLE，然后抄的学长的，于是以后就打算用这个板子搞 Dinic 了。

题目分析：

略

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 100000+100;
struct Info {
    int to, cap, nxt;
} edge[MAX<<1];
int head[MAX], tot, cur[MAX];
int N, M, T;
int level[MAX];
//用前向星建边
void add_edge(int u, int v, int w) {
    edge[tot].to = v;
    edge[tot].cap = w;
    edge[tot].nxt = head[u];
    head[u] = tot++;
    edge[tot].to = u;
    edge[tot].cap = w;
    edge[tot].nxt = head[v];
    head[v] = tot++;
}
//BFS构建层次图
bool bfs(int s, int e) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].to;
            if (edge[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[e] != -1;
}
int dfs(int u, int end, int f) {
    //如果为终点的话就返回流量
    if (u == end) return f;
    int flow = 0, d;
    for (int &i = cur[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to;
        //只由低层次的点向高层次的点增广
        if (edge[i].cap > 0 && level[u] < level[v] && (d = dfs(v, end, min(edge[i].cap, f)))) {
            edge[i].cap -= d;
            edge[i^1].cap += d;
            flow += d;
            f -= d;
            if (!f) break;
        }
    }
    //如果当前点的流量为0，那么排除掉这个点
    if (flow == 0) level[u] = -1;
    return flow;
}
int max_flow(int s, int e) {
    int flow = 0;
    while (bfs(s, e)) {
        memcpy(cur, head, sizeof(head));
        flow += dfs(s, e, INF);
    }
    return flow;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        tot = 0;
        scanf("%d %d", &N, &M);
        int sx = INF, ex = -INF, s, e;
        for (int i = 1; i <= N; i++) {
            head[i] = -1;
            int x, y;
            scanf("%d %d", &x, &y);
            if (x < sx) sx = x, s = i;
            if (x > ex) ex = x, e = i;
        }
        for (int i = 1; i <= M; i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            add_edge(u, v, w);
        }
        printf("%d\n", max_flow(s, e));
    }
}
ACM►图论►网络流

POJ3281 - Dining（EK最大流+模板）

题目链接：

http://poj.org/problem?id=3281

题目大意：

有$N$个牛，$D$种饮料，$F$种食物，每种牛有$D_i$种想喝的饮料，$F_i$种想吃的食物，每种饮料和食物只能分配给一只牛，问最大能使多少头牛满足同时得到喜欢的饮料和喜欢的食物。

解题过程：

还是挺好想的，一下子就想到了，然后2000长度1A美滋滋。

题目分析：

先把每头牛拆成两个点，一个入点，一个出点，连一个容量为1的边。然后在把每头牛想要的食物与他的入点连上，每头牛想要的饮料和他的出点连上。

再建一个原点和终点，原点连上所有的食物，终点连上所有的饮料，最后跑一个最大流就可以了。上述所有的连边容量都是1。

这样建图保证，对于每一个增广路的流量都为$1$，并且都经过一头牛，一个饮料，一个食物，并且每头牛只得到过一次饮料和食物，保证不会重复计算。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 112;
const int INF = 0x3f3f3f3f;

int N, F, D;

struct Info {
    int to, rev, cap;
    Info(int to, int rev, int cap):to(to), rev(rev), cap(cap){}
};

vector<Info> edge[MAX<<2];

void add_edge(int u, int v) {
    edge[u].push_back(Info(v, edge[v].size(), 1));
    edge[v].push_back(Info(u, edge[u].size()-1, 0));
}

int prevv[MAX<<2]; //存每个节点的前驱节点
int preve[MAX<<2]; //当前节点是前驱节点的第几条边连接的
int flow[MAX<<2]; //当前节点的流量

int bfs(int src, int des) {
    queue<int> q;
    q.push(src);
    memset(prevv, -1, sizeof(prevv));
    memset(preve, -1, sizeof(preve));
    memset(flow, 0, sizeof(flow));
    prevv[src] = 0;
    flow[src] = INF; //初始化起点流量为正无穷
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == des) break;
        for (int i =0; i < edge[u].size(); i++) {
            Info & e = edge[u][i];
            //如果有前驱节点，说明已经走过了，就不加入队列了
            if (e.cap > 0 && prevv[e.to] == -1) {
                prevv[e.to] = u;
                preve[e.to] = i;
                //限制流量
                flow[e.to] = min(e.cap, flow[u]);
                q.push(e.to);
            }
        }
    }
    if (prevv[des] == -1) return -1;
    else return flow[des];
}

int max_flow(int src, int des) {
    int sumflow = 0, aug;
    while ((aug =bfs(src, des)) != -1) {
        int k = des;
        //遍历增广的路径
        while (k != src) {
            int last = prevv[k];
            //让路径上的边的容量减少，反向边流量增加
            edge[last][preve[k]].cap -= aug;
            edge[k][edge[last][preve[k]].rev].cap += aug;
            k = last;
        }
        sumflow += aug;
    }
    return sumflow;
}

int main() {
    while (~scanf("%d %d %d", &N, &F, &D)) {
        for (int i = 0; i <= N + F + D + 1; i++) edge[i].clear();
        for (int i = 1; i <= N; i++) {
            int f, d, v;
            scanf("%d %d", &f, &d);
            for (int j = 1; j <= f; j++) {
                scanf("%d", &v);
                v += N*2;
                add_edge(v, i);
            }
            for (int j = 1; j <= d; j++) {
                scanf("%d", &v);
                v += N*2 + F;
                add_edge(i+N, v);
            }
        }
        for (int i = 1; i <= N; i++) {
            add_edge(i, i+N);
        }
        for (int i = 1; i <= F; i++) {
            int v = i + N*2;
            add_edge(0, v);
        }
        for (int i = 1; i <= D; i++) {
            int v = i + N*2 + F;
            add_edge(v, N*2+F+D+1);
        }
        printf("%d\n", max_flow(0, N*2+F+D+1));
    }
}
ACM►数学►数论

UVa 11426 - GCD - Extreme (II)

题目大意：

输入$N$对公式$ \sum ^{n-1} _{i=1} \sum ^{n} _{j=i+1} GCD(i, j) $求和。

解题过程：

一开始就没思路，然后去翻博客，才发现欧拉函数还可以这么用！

题目分析：

首先对内外两层循环交换下：

$\sum^{N-1}_{i=1} \sum^{N}_{j=i+1} GCD(i, j) = \sum^{n}_{j=2}\sum^{j-1}_{i=1}GCD(i,j)$

然后我们把内层循环拆出来，其实就是$f(n) = \sum^{n-1}_{i=1}GCD(i, n)$这样问题就是如何对这个函数求和了。

这时候，如果对每个数都分别跑一个循环肯定是超时，那么我们枚举每个数的因素，并且用素数筛的思想。

首先，记$g(i, n)$ 为满足 $gcd(x, n) = i(i \le x < n)$的$x$个数，那么对于每个数$f(n) = \sum g(i, n) \cdot i$。如何对于$gcd(x, n) = i$两边同时除去$i$，$gcd(x/i, n/i) = 1$，即$g(i, n) = \phi(n/i)$。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 4000001 + 10;

int phi[MAX];
ll ans[MAX];

//欧拉函数打表
void phi_table(int n) {
    memset(phi, 0, sizeof(phi));
    phi[1] = 1;
    for (int i = 2; i < n; i++) if (!phi[i])
            for (int j = i; j <= n; j += i) {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
}

void init() {
    //枚举每个数的因数
    for (int i = 1; i < MAX; i++) {
        for (int j = i + i; j < MAX; j += i) {
            //这里求的是f(j)的其中一个因子
            ans[j] += (ll)i * phi[j / i];
        }
    }
    for (int i = 2; i < MAX; i++) {
        ans[i] += ans[i-1];
    }
}

int main() {
    phi_table(MAX);
    init();
    int n;
    while (cin >> n && n) {
        cout << ans[n] << endl;
    }
}
ACM►数据结构►线段树

SDUTOJ3475 - 最后の汤圆

题目链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/3475.html

题目大意：

给定一个序列$a_1, a_2 \dots a_n$，这个序列构成一个环，首先删掉第$k$个元素，然后从第$k$个元素开始，继续数$a_k$个元素删除掉下一个元素，求最后剩余的一个数的原始下标。

解题过程：

类似约瑟夫环，之前你做过一个非常大的约瑟夫环直接套公式就好了，然后这一个仔细想了一下，删除每一个元素之后，下一个元素的位置不容易确定，感觉不能直接套公式那种，于是朴素的推了一下，还真的是线段树。

题目分析：

刚开始每一个数的下标就对应他是第几个数比如$1,2,3,4,5$。
这里我如果删除第二个数，并且将第二个数及后面的数减一。
得到这个序列$1,1,2,3,4$，这里第一次出现的$1$，依然是第一个数。
假设我这时候再删除第一个数，那么就变成了$0,0,1,2,3$，依然符合上述的规律。

那么我们就可以这样模拟了，维护一个序列，初始化序列的值为对应的下标，每删除一个数，让这个数及后面的数的值减一。

然后找首个出现的时候用二分查找一下就可以，序列操作后也一直都是有序的，在线段树上也容易进行二分。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

#define lson root<<1
#define rson root<<1|1
#define MID int m = (l+r)>>1

const int MAX = 500000+50;

struct Info {
    int v, lazy;
};

Info tree[MAX<<2];
int data[MAX];

Info operator + (const Info &a, const Info &b) {
    Info rst;
    rst.lazy = 0;
    //让根的值为右儿子的值，目的是让根节点的v是维护的这段区间的最大的
    rst.v = b.v;
    return rst;
}

void push_down(int root) {
    if (tree[root].lazy) {
        int lazy = tree[root].lazy;
        tree[lson].lazy += lazy;
        tree[rson].lazy += lazy;
        tree[lson].v -= lazy;
        tree[rson].v -= lazy;
        tree[root].lazy = 0;
    }
}

void build(int root, int l, int r) {
    tree[root].lazy = 0;
    if (l == r) {
        tree[root].v = l;
        return;
    }
    MID;
    build(lson, l, m);
    build(rson, m+1, r);
    tree[root] = tree[lson] + tree[rson];
}

void updata(int root, int l, int r, int ul, int ur) {
    if (ul > r || l > ur) return;
    //对区间进行减一
    if (ul <= l && r <= ur) {
        tree[root].lazy ++;
        tree[root].v --;
        return;
    }
    push_down(root);
    MID;
    updata(lson, l, m, ul, ur);
    updata(rson, m+1, r, ul, ur);
    tree[root] = tree[lson] + tree[rson];
}

int query(int root, int l, int r, int pos) {
    //如果到了叶子节点，那么到找到了答案
    if (l == r) return l;
    push_down(root);
    MID;
    //如果当前位置比左儿子区间内最大的还要大，那么只能去右儿子找
    if (pos > tree[lson].v) return query(rson, m+1, r, pos);
    else return query(lson, l, m, pos);
}

int main() {
    int n, k;
    while (~scanf("%d %d", &n, &k)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", data+i);
        }
        build(1, 1, n);

        //num表示为当前剩余的数字个数
        int num = n;
        //删除到只剩一个数
        while (num > 1) {
            //可能需要数的数字大于当前总共的，进行取模
            k = k % num;
            if (k == 0) k = num;

            //找到当前第k个数字的原始下标
            int index = query(1, 1, n, k);

            //将index及后面的值减一
            updata(1, 1, n, index, n);

            //接下来需要数从第k个数继续数data[index]个数
            //这等价于从第一个数开始数data[index]+k-1个数
            k = data[index] + k - 1;
            num--;
        }

        //最后查找一下剩余的最后一个数的下标并输出
        printf("%d\n", query(1, 1, n, 1));
    }
}
ACM►数学►数论

LightOJ1197 - Help Hanzo（区间素数筛 + 模板）

题目链接：

https://vjudge.net/problem/LightOJ-1197

题目大意：

给出$a,b$求$[a,b]$内素数个数，保证$b - a < 100000$，$1\le a\le b<2^{31}$。

解题过程：

这题有点可惜，没仔细想就去翻书了，挑战第二版 P121，当初这里看过了，以为只有一个埃氏筛法然后跳过了，有点可惜…

题目分析：

首先对于任意的$b$，他的最小质因数一定不会大于$\sqrt {b}$，那么可以用$[2, \sqrt b]$的素数表，去筛掉$[a, b]$区间内的倍数，剩下的就是素数了。

然后用了两种差不多的实现。

这题要注意$1$不是素数！！！！！

AC代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 100000;
const int MAX_INTERVAL = 200000+100;

vector<int> prime;
bool not_prime[MAX];
bool interval[MAX_INTERVAL];

//先筛出小于等于sqrt(b)的素数
void init() {
    for (int i = 2; i < MAX; i++) {
        if (not_prime[i]) continue;
        prime.push_back(i);
        for (int j = i << 1; j < MAX; j += i)
            not_prime[j] = true;
    }
}

int solve(ll a, ll b) {
    memset(interval, 0, sizeof(interval));
    for (int i = 0; i < prime.size(); i++) {
        if ((ll)prime[i] * prime[i] > b) break;
        
        //计算起始的位置，区间内第一个prime[i]的倍数
        ll s = (a + prime[i] - 1) / prime[i];
        //如果算出的s是1的话，那么就是这个素数本身，这种情况不应该筛掉
        if (s < 2) s = 2;
        
        s *= prime[i];
        for (; s <= b; s += prime[i]) {
            interval[s-a] = true;
        }
    }
    
    //最后统计答案
    int ans = 0;
    for (int i = 0; i <= b - a; i++) {
        if (!interval[i]) ans++;
    }
    return ans;
}

int main() {
    int T;
    init();
    scanf("%d", &T);
    for (int Case = 1; Case <= T; Case++) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        int ans = solve(a, b);
        if (a == 1) ans--;
        printf("Case %d: %d\n", Case, ans);
    }
}

AC代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX = 100000;
const int MAX_INTERVAL = 200000+100;

//这个是最终答案的区间
bool not_prime[MAX_INTERVAL];
//这个是小于sqrt(b)的区间
bool not_prime_small[MAX];

int solve(ll a, ll b) {
    memset(not_prime, 0, sizeof(not_prime));
    memset(not_prime_small, 0, sizeof(not_prime_small));

    //枚举所有小于等于sqrt(b)的数
    for (int i = 2; (ll) i * i < b; i++) {
        //如果是素数进行下一步
        if (!not_prime_small[i]) {
            //筛掉小区间内的倍数
            for (int j = 2 * i; (ll)j * j < b; j += i) {
                not_prime_small[j] = true;
            }
            //筛掉大区间内的倍数，找起始位置的方法与第一种一样
            for (ll j = max(2LL, (a + i - 1) / i) * i; j <= b; j += i) {
                not_prime[j - a] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= b - a; i++) {
        if (!not_prime[i]) ans++;
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; Case++) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        int ans = solve(a, b);
        if (a == 1) ans--;
        printf("Case %d: %d\n", Case, ans);
    }
}
ACM►数学

LightOJ1214 - Large Division（高精度取模 + 模板）

题目链接：

https://vjudge.net/problem/LightOJ-1214

题目大意：

两个数$-10^{100}<a<100^{100}$, $b$ 为 32bit范围内(其实并不是)，需要用64位整型才可以。问$a$能否被$b$整除。

解题过程：

先用 Java 的大数类水过了，然后感觉应该用到数论的知识，想起来之前好像也有一道高精度取模的题，当初用 Python 水过去了，现在认真的学一下高精度取模。

题目分析：

显然这题正负号和是否整除无关，先忽略掉。

对于每一个整数，可以分解为如下的形式（以$1234$举例）：
$12345 = ((1\times 10 + 2)\times 10+3)\times10 + 4$
然后这里可以顺带取模（以模123为例）：
$12345\mod 123 = (((1\times 10 \mod 123 + 2)\times 10 \mod 123+3)\times10 \mod 123+ 4)\mod123$

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

char str[1123];
ll mod;

int main() {
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; Case++) {
        scanf("%s %lld", str, &mod);
        int len = strlen(str);
        ll rst = 0;
        //忽略掉负号
        int i = str[0] == '-' ? 1 : 0;
        for (;i < len; i++) {
            rst = ((rst * 10) % mod + (str[i] - '0')) % mod;
        }
        //取模为0表示可以被整除
        if (rst == 0) {
            printf("Case %d: divisible\n", Case);
        }
        else {
            printf("Case %d: not divisible\n", Case);
        }
    }
}
ACM►数学►数论

LightOJ1236 - Pairs Forming LCM（LCM+唯一分解定理）

题目链接：

https://vjudge.net/problem/LightOJ-1236

题目大意：

给定一个数$n$，求满足$i \le j < n \wedge lcm(i, j) = n$的$(i, j)$对总共有多少个。

解题过程：

想了一会…不会，看的博客，就当是个结论好了。

题目分析：

对于每一对$(i, j)$，可由唯一分解定理写成如下形式：
$n = p_1^{e_1} \cdot p_2^{e_2} \dots p_k^{e_k}$
$i = p_1^{a_1} \cdot p_2^{a_2} \dots p_k^{a_k}$
$j = p_1^{b_1} \cdot p_2^{b_2} \dots p_k^{b_k}$

要使得$lcm(i, j) = n$的充要条件是满足$max(a_i, b_i) = c_i$。
那么问题就转化成了找满足上述条件的$(a_i,b_i)$对数，即是 $\small{2} c_i + 1$。

再根据分步乘法算出的即是答案。不过这样对于除了$i = j$的时候，其他的都分别计算了$(i, j), (j, i)$，这里最后答案要除以二并加一。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

const int MAX = 11234567;

typedef long long ll;

vector<int> prime;
bool not_prime[MAX];

void get_prime() {
    for (int i = 2; i < MAX; i++) {
        if (not_prime[i]) continue;
        prime.push_back(i);
        for (int j = i << 1; j < MAX; j += i) {
            not_prime[j] = true;
        }
    }
}

int main() {
    get_prime();
    int T;
    scanf("%d", &T);
    for (int Case = 1; Case <= T; Case++) {
        ll n;
        ll ans = 1;
        scanf("%lld", &n);
        //进行质因子分解，并计算，但是这里素数表只到sqrt(n)
        for (int i = 0; i < prime.size(); i++) {
            if (prime[i] > n) break;
            if (n % prime[i] != 0) continue;
            int cnt = 0;
            while (n % prime[i] == 0) {
                n /= prime[i];
                cnt++;
            }
            ans *= (2 * cnt + 1);
        }
        //如果n不为1，说明还剩下一个大于sqrt(n)的质因子，要当前的结果乘三
        if (n > 1) ans *= 3;
        ans = ans / 2 + 1;
        printf("Case %d: %lld\n", Case, ans);
    }
}
ACM►数学

LightOJ1282 - Leading and Trailing（快速幂+数学）

题目链接：

https://vjudge.net/problem/LightOJ-1282

题目大意：

求$n^k$的前3位数和后三位数。$2\le a<2^{31} , 1\le k \le 10^7$。

解题过程：

只让求后三位的话我到是会，用快速幂就好了，但是求前三位感一脸懵逼。于是去翻了博客，发现居然还有这种操作！

题目分析：

后三位直接用快速幂取膜就好了，这里说一下前三位。

这里先假设：$n^k = a.bc…\times 10^m$，即用科学计数法表示，因为只要前三位，那么接下来就忽略掉后面的位。

对于上式两边同时取$\lg$：$k\lg n = \lg a.bc + m$
这里$m$一定为一个整数，$a.bc$在科学计数法中小于10，那么$\lg a.bc$一定为一个小于$0$的小数。

那么$\lg a.bc$ 为 $k\lg n$ 的小数部分，$m$为$k\lg n$的整数部分。

然后$abc = 10^{\lg a.bc} \times 100$，即为所求的前三位数。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1000;

//快速幂+取模
int pow_mod(int n, int m) {
    int ans = 1, x = n;
    while (m > 0) {
        if (m&1) {
            ans = (ll)ans * x % mod;
        }
        x = (ll) x * x % mod;
        m >>= 1;
    }
    return ans;
}

int main() {
    int T, n, m;
    cin >> T;
    for (int Case = 1; Case <= T; Case++) {
        cin >> n >> m;

        //计算前三位数
        double t = log10(n) * m;
        t -= floor(t);
        int ans1 = pow(10, t)*100;

        int ans2 = pow_mod(n, m);
        printf("Case %d: %d %03d\n", Case, ans1, ans2);
    }
}