首页 > 其他 > 详细

【BZOJ2693】jzptab & 【BZOJ2154】Crash的数字表格

时间:2018-07-20 22:10:36      阅读:29      评论:0      收藏:0      [点我收藏+]

标签:iostream   mod   哪里   isp   pre   printf   type   容易   --   

题目

弱化版题目的传送门(【BZOJ2154】Crash的数字表格)

加强版题目的传送门(【BZOJ2693】jzptab)

思路&解法

题目是要求:
\(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}lcm(i, j)\)

于是我们可以把式子化成这样:
\[\sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{gcd(i, j)}\]

然后我们枚举gcd

\[\sum_{i = 1}^{n}\sum_{j = 1}^{m} \sum_{k = 1}^{min(n, m)}\frac{ij}{k}\]

我们再把式子换一下

\[\sum\limits_{k = 1}^{min(n, m)}{\frac{1}{k}\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{m}ij[gcd(i, j) == k]} \]

\[\sum\limits_{k = 1}^{min(n, m)}{\frac{1}{k}\sum\limits_{i = 1}^{\lfloor{\frac{n}{k}}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{m}{k}\rfloor}ijk^2[gcd(i, j) == 1]} \]

\[\sum^{min(n, m)}_{k = 1}k\sum_{i= 1}^{\lfloor{\frac{n}{k}}\rfloor}\sum_{j = 1}^{\lfloor{\frac{m}{k}}\rfloor}ij[gcd(i, j) ==1]\]

反演一下
\[\sum_{k}^{min(n, m)} k \sum_{d = 1}^{min(\lfloor {\frac{n}{k}} \rfloor, \lfloor {\frac{m}{k}} \rfloor)}\mu(d) \times \sum_{i|d}\sum_{j|d} ij\]

\[\sum_{k}^{min(n, m)} k\sum_{d = 1}^{min(\lfloor {\frac{n}{k}} \rfloor, \lfloor {\frac{m}{k}} \rfloor)} \mu(d) \times d^2\sum_{i=1}^{\lfloor{\frac{n}{kd}}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor} ij\]

\[\sum_{k}^{min(n, m)} k\sum_{d = 1}^{min(\lfloor {\frac{n}{k}} \rfloor, \lfloor {\frac{m}{k}} \rfloor)} \mu(d)d^2 F(\lfloor{\frac{n}{kd}}\rfloor, \lfloor{\frac{m}{kd}}\rfloor)\]

其中\[F(n, m) = {nm(n+1)(m+1)\over 4}\]

继续优化

\[\sum_{T=1}^{min(n, m)}{F(\lfloor{\frac{n}{T}}\rfloor, \lfloor{\frac{m}{T}}\rfloor)}\sum_{d|T}\mu(d)d^2{\frac{T}{d}}\]

后面的\(\sum\limits_{d|T}\mu(d)d^2{\frac{T}{d}}\)的前缀和很容易求

代码

【BZOJ2693】jzptab

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 100000009LL;

const int N = 10000010;

int p[N], total;
bool vis[N];

LL g[N];

void init()
{   g[1] = 1;
    for (int i = 2; i <= 10000000; i++)
    {   if (!vis[i]) p[++total] = i, g[i] = (LL) (1 - i + mod) % mod;
        for (int j = 1; j <= total && i * (LL) p[j] <= 10000000; j++)
        {   vis[i * p[j]] = 1;
            if (i % p[j] == 0) { g[i * p[j]] = g[i]; break; }
            else g[i * p[j]] = (g[i] * g[p[j]]) % mod;
        }
    }
    for (int i = 2; i <= 10000000; i++) g[i] = (g[i] * i + g[i-1]) % mod;
}

LL Get(int n) { return ((LL) n * (LL) (n+1) / 2LL) % mod; }

LL Sum(int n, int m) { return (Get(n) * Get(m)) % mod; }

LL Calc(int n, int m)
{   int last = 0;
    LL Ans = 0;
    for (int i = 1; i <= min(n, m); i = last+1)
    {   last = min(n / (n/i), m / (m/i));
        Ans = (Ans + (Sum(n/i, m/i) * (g[last] - g[i-1])) % mod) % mod;
    }
    return (Ans + mod) % mod;
}

int main()
{   init();
    int T;
    scanf("%d", &T);
    while (T--)
    {   int n, m;
        scanf("%d %d", &n, &m);
        printf("%lld\n", Calc(n, m));
    }
    return 0;
}

【BZOJ2154】Crash的数字表格

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 20101009LL;

const int N = 10000010;

int p[N], total;
bool vis[N];

LL g[N];

void init()
{   g[1] = 1;
    for (int i = 2; i <= 10000000; i++)
    {   if (!vis[i]) p[++total] = i, g[i] = (LL) (1 - i + mod) % mod;
        for (int j = 1; j <= total && i * (LL) p[j] <= 10000000; j++)
        {   vis[i * p[j]] = 1;
            if (i % p[j] == 0) { g[i * p[j]] = g[i]; break; }
            else g[i * p[j]] = (g[i] * g[p[j]]) % mod;
        }
    }
    for (int i = 2; i <= 10000000; i++) g[i] = (g[i] * i + g[i-1]) % mod;
}

LL Get(int n) { return ((LL) n * (LL) (n+1) / 2LL) % mod; }

LL Sum(int n, int m) { return (Get(n) * Get(m)) % mod; }

LL Calc(int n, int m)
{   int last = 0;
    LL Ans = 0;
    for (int i = 1; i <= min(n, m); i = last+1)
    {   last = min(n / (n/i), m / (m/i));
        Ans = (Ans + (Sum(n/i, m/i) * (g[last] - g[i-1])) % mod) % mod;
    }
    return (Ans + mod) % mod;
}

int main()
{   init();
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%lld\n", Calc(n, m));
    return 0;
}

一些其他的东西

弱化版题目可以\(O(n)\)过, 然而我是用\(O(\sqrt{n})\)的算法做的, 而且达到了惊人的18s, 比\(O(n)\)的解法慢多了。我哪里写锉了。。。。。。

【BZOJ2693】jzptab & 【BZOJ2154】Crash的数字表格

标签:iostream   mod   哪里   isp   pre   printf   type   容易   --   

原文:https://www.cnblogs.com/2016gdgzoi509/p/9343688.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号