可以回顾的题目:

  • 023 线性筛法的拓展
  • 024 康托展开+树状数组
  • 026 除法，循环节的一些问题
  • 029 溢出问题，非常吐血，高精度都打不过系列

021

思路

AC Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int dp[N];

void init(int n){
    int s = 0;
    for(int i = 1; i <= n / i; i++){
        if(n % i) continue;
        if(i * i == n) s += i;
        else s += (i + n / i);
    }
    dp[n] = s - n;
}

int main() {
    for(int i = 1; i < N; i++) init(i);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int res = 0;
        for(int i = 1; i <= n; i++){
            int a = i;
            int b = dp[a];
            if(a != b && b < N && dp[b] == a) res += a;
        }
        cout << res << endl;
    }
    return 0;
}

022

思路

略

AC Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<string> a;
string b;
int n, q;

int find(string s){
    int l = 0, r = n - 1;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(a[mid] == s) return mid;
        if(a[mid] > s) r = mid - 1;
        else l = mid;
    }
    return l;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> b;
        a.push_back(b);
    }
    sort(a.begin(), a.end());
    cin >> q;
    while(q--){
        cin >> b;
        int res = 0;
        for(auto c : b) res += c - 'A' + 1;
        int id = find(b) + 1;
        cout << res * id << endl;
    }
    return 0;
}

023

思路

线性筛的应用，包括因数个数等解法，非常有用。

推荐博客。

线性筛法

AC Code

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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int N = 100010;
int f[N], g[N];
int primes[N];
bool st[N];
int cnt;

set<int> s;

void init(){
    f[1] = g[1] = 1;
    for(int i = 2; i <= N; i++){
        if(!st[i]){
            primes[cnt++] = i;
            f[i] = 1 + i;
            g[i] = 1 + i;
        }
        for(int j = 0; primes[j] <= N / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0){
                g[i * primes[j]] = g[i] * primes[j] + 1;
                f[i * primes[j]] = f[i] / g[i] * g[i * primes[j]];
                break;
            }
            g[i * primes[j]] = primes[j] + 1;
            f[i * primes[j]] = f[i] * g[i * primes[j]];
        }
        if(f[i] - i > i) s.insert(i);
    }
}

int main() {
    init();
    //for(auto c : s) cout << c << " ";
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        bool flag = false;
        for(auto c : s){
            if(c < n && s.count(n - c)){
                flag = true;
                break;
            }
        }
        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

024

思路

康托展开和逆康托展开OI-wiki

一个非常amazing的东西Factorial_number_system

树状数组还忘记差不多了，难受

AC Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;
const int N = 16;
ll dp[N], a[N], c[N];

int lowbit(int x){
    return x & -x;
}

void add(int x, int y){
    for(int i = x; i <= 13; i += lowbit(i)) c[i] += y;
}

int sum(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

int main() {
    dp[0] = 1;
    for(int i = 1; i <= 13; i++) dp[i] = dp[i - 1] * i;
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        n -= 1;
        for(int i = 1; i <= 13; i++) add(i, 1);
        for(int i = 1; i <= 13; i++){
            int k = n / dp[13 - i] + 1;
            n %= dp[13 - i];
            int l = 1, r = 13;
            while(l < r){
                int mid = (l + r) >> 1;
                if(sum(mid) >= k) r = mid;
                else l = mid + 1;
            }
            a[i] = r;
            add(r, -1); 
            // cout << k << " "  << n << " " << a[i] << " " << endl;
        }
        for(int i = 1; i <= 13; i++) cout << (char)('a' + a[i] - 1);
        cout << endl;
    }
    return 0;
}

025

思路

记忆化，思路比较简单，实现一下高精度加法

AC Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> add(vector<int> a, vector<int> b){
    int alen = a.size();
    int blen = b.size();
    vector<int> c;
    for(int i = 0, carry = 0; i < alen || i < blen || carry; i++){
        if(i < alen) carry += a[i];
        if(i < blen) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

int main() {
    int t;
    cin >> t;
    vector<vector<int>> s;
    s.push_back({0});
    s.push_back({1});
    while(t--){
        int n;
        cin >> n;
        if(s.back().size() >= n){
            int l = 1, r = s.size() - 1;
            while(l < r){
                int mid = (l + r) >> 1;
                if((int)s[mid].size() >= n) r = mid;
                else l = mid + 1;
            }
            cout << r << endl;
        }else{
            while((int)s.back().size() < n){
                int k = s.size();
                s.push_back(add(s[k - 2], s[k - 1]));
            }
            cout << s.size() - 1 << endl;
        }
    }
    return 0;
}

026

思路

非常有趣，补充几道题

Code

这题评测机有点搞笑，一次性计算可以过，根据n计算反而不可以过，离谱到家。

此外用unordered_map也可以过。

即f函数实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int x){
    unordered_map<ll, int> mp;
    int pos = 0;
    ll a = 1ll;
    while(a){
        if(mp.count(a)){
            return pos - mp[a];
        }
        mp[a] = pos;
        a = a * 10 % x;
        pos++;
    }
    return 0;
}

TLE Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
using namespace std;
using ll = long long;

const int N = 10010;
int d[N];
int s[N];
int pos[N];
int cnt;

int f(int x){
    memset(pos, 0, sizeof(pos));
    int p = 0;
    ll a = 1ll;
    while(a){
        if(pos[a]){
            return p - pos[a];
        }
        pos[a] = p;
        a = a * 10 % x;
        p++;
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    cnt = 3;
    d[3] = 1;
    s[3] = 3;
    while(t--){
        int n;
        cin >> n;
        if(cnt < n - 1){
            for(int i = cnt + 1; i < n; i++){
                d[i] = f(i);
                //cout << i << " : " << d[i] << endl; 
                s[i] = d[i] > d[s[i - 1]] ? i : s[i - 1];
            }
        }
        cout << s[n - 1] << endl;
    }
    return 0;
}

AC Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
using namespace std;
using ll = long long;

const int N = 10010;
int d[N];
int s[N];
int pos[N];
int cnt;

int f(int x){
    memset(pos, 0, sizeof(pos));
    int p = 0;
    ll a = 1ll;
    while(a){
        if(pos[a]){
            return p - pos[a];
        }
        pos[a] = p;
        a = a * 10 % x;
        p++;
    }
    return 0;
}

int main() {
    int t;
    cin >> t;
    cnt = 3;
    d[3] = 1;
    s[3] = 3;
    for(int i = 4; i < 10000; i++){
        d[i] = f(i);
        s[i] = d[i] > d[s[i - 1]] ? i : s[i - 1];
    }
    while(t--){
        int n;
        cin >> n;
        cout << s[n - 1] << endl;
    }
    return 0;
}

027

思路

暴力枚举

n = 0, s = b;

n = 1, s = 1 + a + b

因此b , 1+ a + b起码为素数，可以简化很多

continue不要搞成break就行了。。。

AC Code

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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 4020;
int primes[N];
bool st[N];
int cnt;

void init(){
    st[1] = st[0] = true;
    for(int i = 2; i < N; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; primes[j] < N / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

int f(int a, int b, int n){
    return n * n + n * a + b;
}

bool isPrime(int x){
    if(x <= 1) return false;
    if(x < N) return !st[x];
    for(int i = 2; i <= x / i; i++){
        if(x % i == 0) return false;
    }
    return true;
}

int main() {
    init();
    int n;
    cin >> n;
    int mx = 0;
    int ra = -1, rb = -1;
    for(int a = -n; a <= n; a++){
        for(int b = -n; b <= n; b++){
            if(st[b]) continue;
            if(st[1 + a + b]) continue;
            int k = 0;
            while(1){
                int s = f(a, b, k);
                //cout << a << " "  << b << " " << s<<endl;
                if(!isPrime(s)) break;
                k++;
            }
            if(k > mx){
                ra = a;
                rb = b;
                mx = k;
            }
        }
    }
    cout << ra << " " << rb << endl;
    return 0;
}

028

思路

有点吐血，全程高精度，但是最后一个TLE。。。

Code

TLE Code

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;
const int N = 1e9 + 7;

vector<int> mull(vector<int> a, int b){
    vector<int> c;
    int n = a.size();
    for(int i = 0, carry = 0; i < n || carry; i++){
        if(i < n) carry += a[i] * b;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

vector<int> add(vector<int> a, vector<int> b){
    vector<int> c;
    for(int i = 0, carry = 0; i < a.size() || i < b.size() || carry; i++){
        if(i < a.size()) carry += a[i];
        if(i < b.size()) carry += b[i];
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

vector<int> mul(vector<int> a, vector<int> b){
    vector<int> c = {0};
    for(int i = 0; i < b.size(); i++){
        auto res = mull(a, b[i]);
        for(int j = 0; j < i; j++) res.insert(res.begin(), 0);
        c = add(c, res);
    }
    return c;
}

vector<int> sub(vector<int> a, int b){
    for(int i = 0, r = b; i < a.size(); i++){
        if(a[i] >= r){
            a[i] -= r;
            break;
        }
        a[i] = (a[i] + 10 - r);
        r = 1;
    }
    return a;
}

vector<int> div(vector<int> a, int b){
    vector<int> c;
    for(int i = a.size() - 1, r = 0; i >= 0; i--){
        r = r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    reverse(c.begin(), c.end());
    while(c.size() > 0 && c.back() == 0) c.pop_back();
    return c;
}

ll div2(vector<int> a, ll b){
    vector<int> c;
    ll r = 0;
    for(int i = a.size() - 1; i >= 0; i--){
        r =  r * 10 + a[i];
        c.push_back(r / b);
        r %= b;
    }
    return r;
}


ll f(ll a){
    // (4n^3 + 3n^2 + 8n - 9) / 6
    if(a == 1) return 1;
    vector<int> n1;
    while(a){
        n1.push_back(a % 10);
        a /= 10;
    }
    auto n2 = mul(n1, n1);
    auto n3 = mul(n2, n1);
    auto s1 = mull(n3, 4);
    auto s2 = mull(n2, 3);
    auto s3 = mull(n1, 8);
    auto res = add(s1, s2);
    res = add(res, s3);
    res = sub(res, 9);
    res = div(res, 6);
    ll r = div2(res, N);
    return r;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}

AC Code

答案

不好整，令 $k = (n - 1) / 2 = \lfloor n/2 \rfloor$，即 $n = 2k + 1$

从而化为

这可以先求每一项取模后的结果，其中 $\frac{8k(k+1)(2k+1)}{3}$ 可以对k三分类讨论去掉从而去掉分母。

然后$k * k$ 量级依然可能溢出，因此需要对 $k, k + 1$等先取模后相乘。

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
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = unsigned long long;
const int mod = 1e9 + 7;

ll g(ll n){
    ll res = 1;
    ll k = n / 2;
    res = (res + k % mod * 4 % mod) % mod;
    res = (res + k % mod * 2 % mod * ((k + 1) % mod)) % mod;
    if(k % 3 == 0){
        res = (res + (k / 3) % mod * 8 % mod * ((k + 1) % mod) % mod * ((2 * k + 1) % mod)) % mod;
    }else if(k % 3 == 1){
        res = (res + k % mod * 8 % mod * ((k + 1) % mod) % mod * ((2 * k + 1) / 3 % mod)) % mod;
    }else{
        res = (res + k % mod * 8 % mod * ((k + 1) / 3 % mod) % mod * ((2 * k + 1) % mod)) % mod;
    }
    return (res + mod) % mod;
}

int main() {
    int t;
    cin >> t;
    while(t--){
        ll n;
        cin >> n;
        cout << g(n) << endl;
    }
    return 0;
}

029

思路

AC Code

1
#

030

思路

AC Code

1
#