2020 CCPC网络赛 Graph Theory Class(min

题意:
1 − n 1-n 1n的最小生成树,边权为 l c m ( i + 1 , j + 1 ) lcm(i+1,j+1) lcm(i+1,j+1) i , j i,j i,j属于 1 − n 1-n 1n
思路:
这个规律其实很简单推,就是让所有点和2连接,这样生成树的权值最小,但存在个问题,就是素数和合数与 2 2 2 l c m lcm lcm不一样,这样就需要分开来求,所以问题就演变成如何快速求 1 − 1 e 10 1-1e10 11e10以内的素数前缀和,然后就引出一个算法 m i n 25 min25 min25算法,时间复杂度是 O ( 0.75 N ) O(0.75N) O(0.75N),显然是可以达到题目要求的时间复杂度的,所以扔一个板子这题就可以过了。

参考代码:

/*
 * @Author: vain
 * @Date: 2020
 * @LastEditTime: 2020-09-22 11:55:05
 * @LastEditors: sueRimn
 * @Description: 学不会 dp 的 fw
 * @FilePath: \main\demo.cpp
 */
//#include bits/stdc++.h
#include cstdio
#include algorithm
#include iostream
#include vector
#include map
#include queue
#include set
#include ctime
#include cstring
#include cstdlib
#include math.h
#include bitset
using namespace std;
typedef long long ll;
#define ll long long
//typedef unsigned long long uint;
const int N = 1e3 + 20;
const int maxn = 1e7 + 20;
// typedef pairint, int p;
// priority_queuep, vectorp, greaterp m;
//int sum[maxn];
ll mod;
int max(int a, int b) { return a  b ? a : b; }
int min(int a, int b) { return a  b ? a : b; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
void swap(int x, int y) { x ^= y, y ^= x, x ^= y; }
//int ik[N], q[N], cnt;
int lowbit(int x) { return (x)  (-x); }
//vectorint f;
int h[maxn], p[maxn];
const int base = 13331;
char s[maxn];
ll ksm(ll a, ll b)
{
    ll res = 1;
    a %= mod;
    while (b)
    {
        if (b % 2 == 1)
            res = (a * res) % mod;
        b = 1ll;
        a = (a % mod) * (a % mod) % mod;
    }
    return res;
}
int ksc(int x, int y, int mod)
{
    return (x * y - (int)((long double)x / mod * y) * mod + mod) % mod;
}

ll prime[maxn], id1[maxn], id2[maxn], flag[maxn], ncnt, m;

ll g[maxn], sum[maxn], a[maxn], T, n;

inline int ID(ll x)
{
    return x = T ? id1[x] : id2[n / x];
}

inline ll calc(ll x)
{
    return x * (x + 1) / 2 - 1;
}

inline ll f(ll x)
{
    return x;
}

inline void init()
{
    T = sqrt(n + 0.5);
    for (int i = 2; i = T; i++)
    {
        if (!flag[i])
            prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
        for (int j = 1; j = ncnt  i * prime[j] = T; j++)
        {
            flag[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    for (ll l = 1; l = n; l = n / (n / l) + 1)
    {
        a[++m] = n / l;
        if (a[m] = T)
            id1[a[m]] = m;
        else
            id2[n / a[m]] = m;
        g[m] = calc(a[m]);
    }
    for (int i = 1; i = ncnt; i++)
        for (int j = 1; j = m  (ll)prime[i] * prime[i] = a[j]; j++)
            g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}

inline ll solve(ll x)
{
    if (x = 1)
        return x;
    return n = x, init(), g[ID(n)];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    // srand(time(unsigned int));
    int t;
    cin  t;
    //Sum(10000);
    while (t--)
    {
        ncnt = m = 0;
        cin  n  mod;

        ll s = ((3ll + (n % mod)) * (n % mod) % mod) * ksm(2, mod - 2) % mod;
        //cout  sum  endl;
        ll x = solve(n + 1ll) % mod;
        //cout  x  endl;
        ll ans = (s - x + mod) % mod;
        x = (x - 2 + mod) % mod;
        ll res = ((x * 2ll % mod) + ans) % mod;
        cout  res  endl;
    }
}
最新回复(0)
/jishu5xf1lYL4Ht61KJnc0nlSHQkKkcW4QOUhnjt_2Fxmq5J_2FU_3D4794919
8 简首页