【题解】2021 CCPC 新疆省赛

Problem A. balloon

将两个序列从小到大排序,从跳跃高度较低的人考虑到跳跃高度较高的人,使用一个变量 ​​​ 维护当前取到的气球,若气球能取就取,不能取就换成下一个人。

时间复杂度的瓶颈在于排序。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 2e5 + 10;
int n, m;
struct Node {
    int h;
    int id;
} e[N];
int ans[N];
int h[N];
bool cmp(Node a, Node b) {
    return a.h < b.h;
}
void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++) {
        cin >> e[i].h;
        e[i].id = i;
    }
    sort(e + 1, e + 1 + n, cmp);

    for(int i = 1; i <= m; i ++)
        cin >> h[i];
    int now  = 1;
    sort(h + 1, h + 1 + m);
    for(int i = 1; i <= n; i ++) {
        int num = 0;
        while(now <= m && h[now] <= e[i].h)
            num ++, now ++;
        ans[e[i].id] = num ;
    }
    for(int i = 1; i <= n; i ++)
        cout << ans[i] << endl;
    return ;
}
signed main() {
    int t = 1;
    while(t--)
        solve();
    return 0;
}

Problem B. sophistry

可以从后往前倒序 dp。

表示:考虑到了第 天到第 天时,造成的最大伤害。

  • 时,有转移:
  • 时,有转移:

最后答案即为 ​,时间复杂度 ​。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
ll dp[maxn];
ll a[maxn];
int main()
{
    int n,d,m;
    scanf("%d%d%d",&n,&d,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    for(int i=n;i>=1;i--)
    {
        if(a[i]>m)
        {
            dp[i]=max(dp[i+d+1]+a[i],dp[i+1]);
        }
        else
        {
            dp[i]=dp[i+1]+a[i];
        } 
    }
    cout<<dp[1]<<endl;
}

Problem C. bomb

先考虑一下没有环的情况。

结论:答案为有向图的最长链长度。

证明:

  • 由于最长链上的点两两不能在同一轮染色。所以最优解 最长链长度。

  • ​​ 表示从 ​​ 开始的最长链长度,可以在第 ​​ 轮中对所有 ​​ 的点 ​​ 进行染色,恰好可以得到一个轮数为最长链长度的方案。所以最优解 ​​ 最长链长度。

故答案为有向图的最长链长度。

再考虑一下有环的情况。

考虑使用 tarjan 将这张有向图中的所有强连通分量求出,那么对于任意一个强连通分量,如果在一轮染色中对这个强连通分量中的其中一个点进行染色,那么这个强连通分量中的其他点、以及它所能到达的强连通分量里的所有点都不能染色。

我们发现这与题目的定义类似,对于一个大小为 的强连通分量,可以将其缩为一个需要被染色 次的点。这样就得到了一张新图,答案即为这张新图中的最长链,使用拓扑排序即可解决。

时间复杂度 ​。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 2e6 + 10;
int e[N], h[N], ne[N], idx;
int cnt;
int stk[N];
int top;
int in_stk[N];
int dfn[N];
int low[N];
int scc_cnt;
int in_scc_num[N];
int scc_size[N];
int n, m;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++ cnt;
    stk[++ top] = u;
    in_stk[u] = 1;

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];

        if(!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);

        } else if(in_stk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(dfn[u] == low[u]) {
        scc_cnt ++;
        int x;
        do {
            x = stk[top --];
            in_stk[x] = 0;
            in_scc_num[x] = scc_cnt;
            scc_size[scc_cnt] ++;
        } while(x != u);
    }

}



int h1[N], e1[N], ne1[N], idx1;
int du[N];
void add1(int a, int b) {

    e1[idx1] = b;
    ne1[idx1] = h1[a];
    h1[a] = idx1 ++;
    du[b] ++;

}


ll dist[N];


void topsort() {
    queue<int>q;


    for(int i = 1; i <= scc_cnt; i ++)
        if(du[i] == 0)
            q.push(i), dist[i] = scc_size[i];

    while(q.size()) {
        int u = q.front();
        q.pop();
        for(int i = h1[u]; i != -1; i = ne1[i]) {
            int v = e1[i];
            dist[v] = max(dist[v], dist[u] + scc_size[v]);
            if(--du[v] == 0)
                q.push(v);
        }
    }
}
void solve() {
    cin >> n >> m;
    idx = idx1 = 0;
    memset(h, -1, sizeof h);
    memset(h1, -1, sizeof h1);
    for(int i = 1; i <= m; i ++) {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    for(int i = 1; i <= n ; i++) {
        if(!dfn[i])
            tarjan(i);
    }

    for(int u = 1; u <= n; u ++) {
        for(int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if(in_scc_num[u] == in_scc_num[v])
                continue;

            add1(in_scc_num[u], in_scc_num[v]);

        }
    }

    topsort();
    ll ans = 0;
    for(int i = 1; i <= scc_cnt; i ++)
        ans = max(ans, dist[i]);

    cout << ans << "\n";

    return ;
}
signed main() {
    int t = 1;
    while(t--)
        solve();
    return 0;
}

Problem D

题目要求的就是前 大子段和。

因为 为非负整数,所以如果当前最大的是 子段,那么易得 子段和 子段一定之前就已经取出。

最大的子段一定为 ,所以首先将 加入堆。设堆顶为 ,则 可以成为备选答案,加入堆并用 map 判重即可。

时间复杂度

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;

typedef pair<int, int> pii;
int n, w;
ll a[N];
ll sum;
map<pii, bool>mp;
struct node {
    int l, r;
    ll sum;
    friend bool operator < (node x, node y) {
        return x.sum < y.sum;
    }

};
priority_queue<node>q;
void solve() {
    cin >> n >> w;
    for(int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    q.push({1, n, sum});
    mp[ {1, n}] = 1;
    while(w) {
        auto now = q.top();
        q.pop();
        w--;
        cout << now.sum << " ";
        if(now.l != now.r) {
            if(!mp[ {now.l + 1, now.r}])
                q.push({now.l + 1, now.r, now.sum - a[now.l]});
            if(!mp[ {now.l, now.r - 1}])
                q.push({now.l, now.r - 1, now.sum - a[now.r]});
            mp[ {now.l + 1, now.r}] = mp[ {now.l, now.r - 1}] = 1;
        }
    }
    return ;
}
signed main() {
    int t = 1;
    while(t--)
        solve();
    return 0;
}

Problem E. maxsum

分别为两个数组的最大值,则
另一方面,如果 ,则对应的 都非零。
根据题意,两个数组最多只有 个数非零,暴力计算即可。

时间复杂度

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int a[N];
int b[N];
int c[N];
int n;
int nexta[N];
int nextb[N];
int maxv = 0;
void solve() {
    cin >> n;
    for(int i = 0; i <= n - 1; i ++)
        cin >> a[i], maxv = max(maxv, a[i]);

    for(int i = 0; i <= n - 1; i ++)
        cin >> b[i], maxv = max(maxv, b[i]);

    for(int i = 0; i < n; i ++)
        c[i] = maxv;
    nexta[n - 1] = nextb[n - 1] = n;
    for(int i = n - 1; i >= 1; i --) {
        if(a[i])
            nexta[i - 1] = i;
        else
            nexta[i - 1] = nexta[i];
    }

    for(int i = n - 1; i >= 1; i --) {
        if(b[i])
            nextb[i - 1] = i;
        else
            nextb[i - 1] = nextb[i];
    }


    for(int i = 0 ; i < n; i = nexta[i])
        for(int j = 0; j < n; j = nextb[j])
            c[(i + j) % n] = max(c[(i + j) % n], a[i] + b[j]);

    for(int i = 0; i < n ; i++)
        cout << c[i] << " ";
    cout << "\n";
    return ;

}
signed main() {
    int t = 1;
    while(t--)
        solve();
    return 0;
}

Problem F. fare

​​ 是树的一个结点,设 ​​ 分别表示以 ​​ 为根的子树内所有参加活动的选手到 ​​ 的距离的零次方和,一次方和,二次方和,再设 ​​ 分别表示除去以 ​​ 为根的子树内所有参加活动的选手到 ​​ 的距离的零次方和,一次方和,二次方和。

遍历整棵树就可以求出所有结点的 ​​​,再次遍历整棵树,我们使用换根 的方法,就可以求出所有结点的 ​​​,最后的答案便为

时间复杂度 ​。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
const int mod = 1e9 + 7;
int h[N], e[N], ne[N], idx, w[N];
ll c[N];
ll num1[N];// num
ll num2[N];// edge*num
ll dp1[N];// 1 as root

ll tmp1[N];
ll tmp2[N];
ll dp2[N];//change root

ll n;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa) {
    num1[u] = c[u];

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(v == fa)
            continue;

        dfs1(v, u);

        num1[u] += num1[v];
        num2[u] += num2[v] + w[i] * num1[v];
        dp1[u] += dp1[v] + 2 * w[i] * num2[v] + w[i] * w[i] * num1[v];
    }




}

void dfs2(int u, int fa) {

    for(int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if(v == fa)
            continue;

        tmp1[v] = num1[u] - num1[v] + tmp1[u];

        tmp2[v] = num2[u] - num1[v] * w[i] - num2[v] + tmp2[u] + tmp1[v] * w[i];

        dp2[v] = dp1[u] - dp1[v] - 2 * w[i] * num2[v] - w[i] * w[i] * num1[v] + dp2[u] +
                 2 * w[i] * (num2[u] - num1[v] * w[i] - num2[v] + tmp2[u] ) 
                 + w[i] * w[i] * tmp1[v];
        dfs2(v, u);


    }
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> c[i];
    idx = 0;
    memset(h, -1 , sizeof h);

    for(int i = 1; i < n; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    dfs1(1, 0);

//    cout << dp1[1] << " ";
    dfs2(1, 0);

    ll ans = 1e18;
    for(int i = 1; i <= n; i++)
        ans = min(ans , dp1[i] + dp2[i]);

    cout << ans << "\n";
    return ;
}
signed main() {
    int t = 1;
    while(t--)
        solve();
    return 0;
}

Problem G. road

注意到异或不进位,每位之间是相互独立的,于是我们可以考虑计算一下每一位的贡献。

比如说我们现在要计算一下第 位的贡献。

设原图中的邻接矩阵为 ,将第 位提取出来可以得到一个 矩阵 。我们让点在新的邻接矩阵上走,注意到按位异或的性质,一条非简单路径只有经过了奇数个边,才会对答案有 的贡献。

考虑 dp。

表示:有多少条 的边数为 的路径,且经过了 偶数 / 奇数 个

则有状态转移方程:
$\text{index}f_{k, T, 1} \ast 2^{\text{index}}$。

直接做的话显然会 TLE,但是这个转移方程对于所有的阶段 转移都一样,于是矩阵快速幂加速即可。

单次回答询问的时间复杂度是 的,其中 表示值域大小。
还不够优秀。

因为回答的询问只关注单源信息,注意到 的矩阵和 的矩阵相乘的复杂度是 的, 的矩阵和 的矩阵相乘的复杂度是 的。

于是我们可以先把 都预处理出来。
然后将 二进制分解,若 的第 位上为 ,则令
这样做的话,单次询问的时间复杂度就成功降到了

总时间复杂度 ​。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

inline int read() {
    int x = 0, f = 1; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
    while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
    return x * f;
}

const int N = 45;
const int mod = 1e9 + 7;

int n, m, Q;
int a[N][N];
int f[31][31][N][N][2];

void mul(int f[N][N][2], int a[N][N][2]) {
    static int c[N][N][2]; memset(c, 0, sizeof(c));

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            for (int k = 1; k <= n; k ++) {
                c[i][j][0] = (c[i][j][0] + 1ll * a[i][k][0] * a[k][j][0]) % mod;
                c[i][j][0] = (c[i][j][0] + 1ll * a[i][k][1] * a[k][j][1]) % mod;
                c[i][j][1] = (c[i][j][1] + 1ll * a[i][k][0] * a[k][j][1]) % mod;
                c[i][j][1] = (c[i][j][1] + 1ll * a[i][k][1] * a[k][j][0]) % mod;
            }

    memcpy(f, c, sizeof(c));
}

void mulstar(int a[N][2], int b[N][N][2]) {
    static int c[N][2]; memset(c, 0, sizeof(c));

    for (int j = 1; j <= n; j ++)
        for (int k = 1; k <= n; k ++) {
            c[j][0] = (c[j][0] + 1ll * a[k][0] * b[k][j][0]) % mod;
            c[j][0] = (c[j][0] + 1ll * a[k][1] * b[k][j][1]) % mod;
            c[j][1] = (c[j][1] + 1ll * a[k][0] * b[k][j][1]) % mod;
            c[j][1] = (c[j][1] + 1ll * a[k][1] * b[k][j][0]) % mod;
        }

    memcpy(a, c, sizeof(c));
}

void calc(int index) {
    for (int u = 1; u <= n; u ++)
        for (int v = 1; v <= n; v ++) {
            if (a[u][v] == 0x3f3f3f3f) continue;
            int w = a[u][v] >> index & 1;
            f[index][0][u][v][w] = 1;
        }

    for (int i = 1; i <= 30; i ++)
        mul(f[index][i], f[index][i - 1]);
}

void work() {
    int S = read(), T = read(), k = read() - 1;
    int ans = 0;

    for (int index = 0; index <= 30; index ++) {
        int d[N][2]; memset(d, 0, sizeof(d));
        for (int i = 1; i <= n; i ++) {
            if (a[S][i] == 0x3f3f3f3f) continue;
            int w = a[S][i] >> index & 1;
            d[i][w] = 1; 
        }

        for (int i = 0; i <= 30; i ++)
            if (k >> i & 1) mulstar(d, f[index][i]);

        ans = (ans + 1ll * (1 << index) * d[T][1]) % mod;
    }

    printf("%d\n", ans);
}

int main() {
    n = read(), m = read();

    memset(a, 0x3f, sizeof(a));
    for (int i = 1; i <= m; i ++) {
        int u = read(), v = read(), w = read();
        a[u][v] = a[v][u] = w;
    }

    for (int index = 0; index <= 30; index ++)
        calc(index);

    Q = read();

    while (Q --)    work();

    return 0;
}

Problem H. xor

按二进制每一位展开:

将原式展开,

枚举 的取值,乘以对应的方案数(即有多少个 满足第 位为 且第 位为 )即可。
预处理出 表示有多少个数满足第 位为 且第 位为 ,则方案数可以查表 得到。
时间复杂度

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
const int mod = 1e9 + 7;
typedef long long ll;
int n;
ll a[N];
ll inv[N];
ll f[40][40][2][2];
signed main() {

    /*
5
12133
544123
47778
69885
11234
    */

    cin >> n;

    for(int i = 1; i <= n; i ++)
        cin >> a[i];


//    ll res = 0 ;
//    for(int i = 1; i <= n; i ++)
//        for(int j = 1; j <= n; j ++)
//            res = (res + (a[i] ^ a[j]) * (a[i] ^ a[j]) % mod) % mod;
//    cout << res << endl;

    inv[0] = 1;
    for(int i = 1; i <= 63; i ++)
        inv[i] = 1ll * 2 * inv[i - 1] % mod;


    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= 31; j ++)
            for(int k = 0; k <= 31; k ++)
                f[j][k][a[i] >> j & 1][a[i] >> k & 1]  ++;


    ll ans = 0;
    for(int i = 0; i <= 31; i ++)
        for(int j = 0; j <= 31; j ++)
            for(int k = 0; k <= 1; k ++)
                for(int z = 0; z <= 1; z ++)
                    ans = (ans + 1ll * f[i][j][k][z] * f[i][j][k ^ 1][z ^ 1] % mod * inv[i + j] % mod) % mod;

    cout << ans << '\n';

    return 0;
}

Problem I. Fibonacci sequence

存在递推式

证明如下

于是可以构建矩阵来优化递推,但是考虑到有 组,我们可以考虑光速幂。

具体来说,我们想要知道 为转移矩阵),我们预处理出矩阵 (其中,)这样,我们就可以 (即矩阵乘法的复杂度) 求出一个 ,进而优化复杂度。

#include <bits/stdc++.h>
#define int long long
const int N = 3 + 10;
const int RN = 1e6 + 10;

using namespace std;

struct matrix
{
    int l, r;
    long long val[N][N];
} a, G, t[100000], t2[100000];

int x[RN];

int G0, G1, M, n, ans = 1;

inline matrix mul(matrix A, matrix B)
{
    matrix C; C.l = A.l, C.r = B.r;
    memset(C.val, 0, sizeof(C.val));

    for (int i = 1; i <= C.l; ++ i)
        for (int j = 1; j <= C.r; ++ j)
            for (int k = 1; k <= A.r; ++ k)
                C.val[i][j] = (C.val[i][j] + A.val[i][k] * B.val[k][j]) % M;

    return C;
}

inline matrix pow(matrix A, int b)
{
    matrix res = A; b --;
    for (; b; b >>= 1)
    {
        if (b & 1) res = mul(res, A);
        A = mul(A, A);
    }
    return res;
}

inline matrix solve(int b)
{
    a.l = 3, a.r = 3;
    a.val[1][1] = 1, a.val[1][2] = 1, a.val[1][3] = 1;
    a.val[2][1] = 1, a.val[2][2] = 0, a.val[3][3] = 0;
    a.val[3][1] = 2, a.val[3][2] = 0, a.val[3][3] = 1;

    return pow(a, b);
}

int Max;

signed main()
{

    cin >> G0 >> G1 >> M >> n;


    G.l = 1, G.r = 3;
    G.val[1][1] = G1, G.val[1][2] = G0, G.val[1][3] = (int)sqrt(3 + G1 * G0) % M;

    a.l = 3, a.r = 3;
    a.val[1][1] = 1, a.val[1][2] = 1, a.val[1][3] = 1;
    a.val[2][1] = 1, a.val[2][2] = 0, a.val[3][3] = 0;
    a.val[3][1] = 2, a.val[3][2] = 0, a.val[3][3] = 1;

    for (int i = 1; i <= n; ++ i)
    {
        cin >> x[i];
        Max = max(Max, x[i]);    
    }
    Max = sqrt(Max) + 1;
    t[1] = solve(1);
    for (int i = 2; i <= Max; ++ i)
        t[i] = mul(t[i - 1], t[1]);
    t2[1] = solve(Max);
    for (int i = 2; i <= Max; ++ i)
        t2[i] = mul(t2[i - 1], t2[1]);
    for (int i = 1; i <= n; ++ i)
    {
        if (x[i] == 0) 
            ans = ans * G0 % M;
        else if (x[i] == 1) 
            ans = ans * G1 % M;
        else
        {
            x[i] -= 1;
            int s = x[i] / Max;
            matrix c1 = t2[s], c2 = t[x[i] - Max * s];
            matrix res = mul(c1, c2);
            if (s == 0) res = c2;
            if (x[i] - Max * s == 0) res = c1;
            ans = ans * mul(G, res).val[1][1] % M;
        }
    }
    cout << ans << endl;

    return 0;
} 

Problem J. mesh

直接上莫比乌斯反演:


,则式子化简为:
(这里的 是狄利克雷卷积,下文同),则式子化简为:
注意到函数 显然为积性函数,可以使用线性筛将 的前缀和筛出。

配合数论分块即可做到 预处理、 回答询问。但还不够优秀。


可以考虑杜教筛,设:
,其中函数 ,显然函数 为约数个数函数。

那么可以得到 有关 的递推式:
化简:
该式显然需要数论分块来做。取一个阈值 ,分段处理:

  • 对于 的部分,使用线性筛求出每个
  • 对于 的部分,使用数论分块求解 ,使用上述递推式求解

可以使用积分近似证明当 时,取到杜教筛的理论最优复杂度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <ctime>

using namespace std;

const int N = 1000100, SIZE = 1e6;
const int mod = 1e9 + 7;

int n, m;

int k, prime[N], low[N];
int h[N], d[N];
int Sd[N], Sh[N];

void GetPrimes(int N) {
    h[1] = 1, d[1] = 1;

    for (int i = 2; i <= N; i ++) {
        if (!low[i]) {
            prime[++ k] = i;
            low[i] = i;
            d[i] = 2;
            h[i] = i - 2;

            if (1ll * i * i <= N) {
                low[i * i] = i * i;
                d[i * i] = 3;
                h[i * i] = (i * i - i) - (i - 1);

                long long v = 1ll * i * i * i;
                int c = 3;

                while (v <= N) {
                    low[v] = v;
                    d[v] = c + 1;
                    h[v] = h[v / i] * i;

                    v *= i, c ++;
                }
            }
        }

        for (int j = 1; j <= k; j ++) {
            if (prime[j] > N / i) break;

            if (i % prime[j] == 0)
                low[i * prime[j]] = low[i] * prime[j];
            else
                low[i * prime[j]] = prime[j];

            d[i * prime[j]] = d[(i * prime[j]) / low[i * prime[j]]] * d[low[i * prime[j]]];
            h[i * prime[j]] = h[(i * prime[j]) / low[i * prime[j]]] * h[low[i * prime[j]]];

            if (i % prime[j] == 0) break;
        }
    }

    for (int i = 1; i <= N; i ++)
        Sd[i] = (Sd[i - 1] + d[i]) % mod,
        Sh[i] = (Sh[i - 1] + h[i]) % mod;
}

map<int, int> Gd, Gh;

int sig(int n) {
    if (n <= SIZE) return Sd[n];
    if (Gd[n]) return Gd[n];
    int ans = 0;
    for (int x = 1, Nx; x <= n; x = Nx + 1) {
        Nx = n / (n / x);
        ans = (ans + 1ll * (Nx - x + 1) * (n / x)) % mod; 
    }
    return Gd[n] = ans;
}

int S(int n) {
    if (n <= SIZE) return Sh[n];
    if (Gh[n]) return Gh[n];
    int ans = (1ll * n * (n + 1) / 2) % mod;
    int sub = 0; 
    for (int x = 2, Nx, cur; x <= n; x = Nx + 1) {
        Nx = n / (n / x);

        cur = ((sig(Nx) - sig(x - 1)) % mod + mod) % mod;
        cur = 1ll * cur * S(n / x) % mod;

        sub = (sub + cur) % mod;
    }
    ans = ((ans - sub) % mod + mod) % mod;
    return Gh[n] = ans;
}

int main() {
    cin >> n >> m;

    GetPrimes(SIZE);

    int ans = 0;
    for (int x = 1, Nx, cur; x <= min(n, m); x = Nx + 1) {
        Nx = min(n / (n / x), m / (m / x));

        cur = ((S(Nx) - S(x - 1)) % mod + mod) % mod;
        cur = 1ll * cur * (n / x) % mod;
        cur = 1ll * cur * (m / x) % mod;

        ans = (ans + cur) % mod;
    }

    cout << ans << endl;

    return 0;
}
全部评论

相关推荐

17 9 评论
分享
牛客网
牛客企业服务