题目#

A. The beautiful values of the palace#

知识点：坐标映射，离散化，树状数组，离线查询

坐标映射#

找一下规律。（虽然我不太会找这个规律

1
ll get_int(int n, int x, int y){
2
    x = x - n/2 - 1;
3
    y = y - n/2 - 1;
4
    ll t = max(abs(x), abs(y));
5
    if(x >= y)  return 1ll * n * n - 4 * t * t - 2 * t - x - y;
6
    else return 1ll * n * n - 4 * t * t + 2 * t + x + y;
7
}

离散化和离线查询#

只离散化一维就行了，当然两个维度都离散化也是没有问题的。

假设只离散化x轴，那么我们对建点和查询操作进行x优先排序，扫描x轴，当操作的x与当前枚举的x相同时进行操作，优先建点，然后查询。这样是为了保证顺序。

查询的时候，相当于查询一个一维前缀和，用树状数组维护就可以了。

1
#include<bits/stdc++.h>
2
#define rep(i, a, b)    for(int i = (a); i <= (int)(b); ++i)
3
#define per(i, a, b)    for(int i = (a); i >= (int)(b); --i)
4
#define debug(x)    cerr << #x << ' ' << x << endl;
5
using namespace std;
6

7
typedef long long ll;
8
const int MAXN = 1e5 + 7;
9
const int MOD = 998244353;
10

11
struct node{
12
    int x, y, id;
13
    ll val;
14
    friend bool operator <(const node &a, const node &b){
15
        return a.x < b.x;
16
    }
17
}s[MAXN], need[MAXN * 4];
18

19
struct ask{
20
    int a, b, c, d;
21
}op[MAXN];
22

23
ll get_int(int n, int x, int y){
24
    x = x - n/2 - 1;
25
    y = y - n/2 - 1;
26
    ll t = max(abs(x), abs(y));
27
    if(x >= y)  return 1ll * n * n - 4 * t * t - 2 * t - x - y;
28
    else return 1ll * n * n - 4 * t * t + 2 * t + x + y;
29
}
30

31
int get_val(ll val){
32
    int ans = 0;
33
    while(val){
34
        ans += val%10;
35
        val /= 10;
36
    }
37
    return ans;
38
}
39
struct BIT {
40
    int e[MAXN], n;
41
    void clear(){rep(i, 0, n)    e[i] = 0;}
42
    int lowbit(int x){return x & (-x);}
43
    void add(int x, int v){
44
        while(x <= n){
45
            e[x] += v;
46
            x += lowbit(x);
47
        }
48
    }
49
    int get(int x){
50
        int ans = 0;
51
        while(x){
52
            ans += e[x];
53
            x -= lowbit(x);
54
        }
55
        return ans;
56
    }
57
}bit;
58

59
int hx[MAXN * 10], hy[MAXN * 10];
60

61
int main() {
62
    int T;
63
    scanf("%d", &T);
64
    while(T--){
65
        int n, m, p;
66
        scanf("%d %d %d", &n, &m, &p);
67
        vector<int> vx, vy;
68
        rep(i, 1, m){
69
            scanf("%d %d", &s[i].x, &s[i].y);
70
            s[i].val = get_val(get_int(n, s[i].x, s[i].y));
71
            vx.push_back(s[i].x);
72
            vy.push_back(s[i].y);
73
        }
74
        int x1, y1, x2, y2;
75
        rep(i, 0, p-1){
76
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
77
            vx.push_back(x1-1);
78
            vx.push_back(x2);
79
            vy.push_back(y1-1);
80
            vy.push_back(y2);
81
            need[i * 4 + 1] = node{x1-1, y1-1, i * 4 + 1};
82
            need[i * 4 + 2] = node{x1-1, y2, i * 4 + 2};
83
            need[i * 4 + 3] = node{x2, y1-1, i * 4 + 3};
84
            need[i * 4 + 4] = node{x2, y2, i * 4 + 4};
85
            op[i] = ask{i*4 + 1, i*4 + 2, i*4 + 3, i*4 + 4};
86
        }
87
        sort(vx.begin(), vx.end());
88
        vx.erase(unique(vx.begin(), vx.end()), vx.end());
89
        sort(vy.begin(), vy.end());
90
        vy.erase(unique(vy.begin(), vy.end()), vy.end());
91
        rep(i, 0, vx.size()-1){hx[vx[i]] = i + 1;}
92
        rep(i, 0, vy.size()-1){hy[vy[i]] = i + 1;}
93
        rep(i, 1, m){
94
            s[i].x = hx[s[i].x];
95
            s[i].y = hy[s[i].y];
96
        }
97
        rep(i, 0, p-1){
98
            need[i * 4 + 1].x = hx[need[i * 4 + 1].x]; need[i * 4 + 1].y = hy[need[i * 4 + 1].y];
99
            need[i * 4 + 2].x = hx[need[i * 4 + 2].x]; need[i * 4 + 2].y = hy[need[i * 4 + 2].y];
100
            need[i * 4 + 3].x = hx[need[i * 4 + 3].x]; need[i * 4 + 3].y = hy[need[i * 4 + 3].y];
101
            need[i * 4 + 4].x = hx[need[i * 4 + 4].x]; need[i * 4 + 4].y = hy[need[i * 4 + 4].y];
102
        }
103
        sort(s + 1, s + 1 + m);
104
        sort(need + 1, need + 1 + 4 * p);
105
        bit.n = vy.size();
106
        bit.clear();
107
        int cur = 1, curs = 1;
108
        rep(i, 0, vx.size()){
109
            while(curs <= m && s[curs].x == i){
110
                bit.add(s[curs].y, s[curs].val);
111
                curs++;
112
            }
113
            while(cur <= 4 * p && need[cur].x == i){
114
                need[cur].val = bit.get(need[cur].y);
115
                cur++;
116
            }
117
        }
118
        sort(need + 1, need + 1 + 4 * p, [](const node &a, const node &b){return a.id < b.id;});
119
        rep(i, 0, p-1){
120
            printf("%lld\n", need[op[i].a].val + need[op[i].d].val - need[op[i].b].val - need[op[i].c].val);
121
        }
122
    }
123
    return 0;
124
}

B. super_log#

知识点：递归，欧拉函数，欧拉定理

扩展欧拉定理#

$a^b \equiv \begin{cases} a^b & b < \varphi(m) \\ a^{b \bmod \varphi(m) + \varphi(m)} & b \ge \varphi(m) \end{cases}\bmod m$

快速幂#

也不知道为什么，快速幂写成这样就可以直接递归求解了。

这其中一定隐藏了什么不为人知的数论之谜。

1
int up(ll a, int mod){
2
    return a < mod ? a : a % mod + mod;
3
}
4
int qpow(int a, int b, int mod){
5
    int res = 1;
6
    while(b){
7
        if(b&1) res = up(1ll * res * a, mod);
8
        a = up(1ll * a * a, mod);
9
        b >>= 1;
10
    }
11
    return res;
12
}

代码#

1
#include <bits/stdc++.h>
2
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
3
#define per(i, a, b) for(int i = (a); i >= (b); --i)
4
using namespace std;
5

6
typedef long long ll;
7
const int MAXN = 1e6 + 7;
8

9
int pri[MAXN], tot;
10
int phi[MAXN];
11
bool mark[MAXN];
12
void init(){
13
    tot = 0;
14
    phi[1] = 1;
15
    for(int i = 2; i <= 1000000; ++i){
16
        if(!mark[i]){
17
            phi[i] = i - 1;
18
            pri[++tot] = i;
19
        }
20
        for(int j = 1; j <= tot; ++j){
21
            int x = pri[j];
22
            if(i * x > 1000000)    break;
23
            mark[i * x] = 1;
24
            if(i%x == 0){
25
                phi[i*x] = phi[i] * x;
26
                break;
27
            } else {
28
                phi[i*x] = phi[i] * phi[x];
29
            }
30
        }
31
    }
32
}
33

34
int up(ll a, int mod){
35
  return a < mod ? a : a % mod + mod;
36
}
37
int qpow(int a, int b, int mod){
38
  int res = 1;
39
  while(b){
40
    if(b&1)  res = up(1ll * res * a, mod);
41
    a = up(1ll * a * a, mod);
42
    b >>= 1;
43
  }
44
  return res;
45
}
46

47
int solve(int a, int b, int m){
48
  //calculate a^a^...^a mod m
49
  //      |<- b ->|
50
  if(!b || m == 1)  return 1;
51
  return qpow(a, solve(a, b-1, phi[m]), m);
52
}
53

54
int main()
55
{
56
  init();
57
  int T, a, b, m;
58
  scanf("%d", &T);
59
  while(T--){
60
    scanf("%d %d %d", &a, &b, &m);
61
    printf("%d\n", solve(a, b, m) % m);
62
  }
63
  return 0;
64
}