首页 > 其他分享 >【NOI2010】能量采集 题解

【NOI2010】能量采集 题解

时间:2024-05-25 16:58:58浏览次数:25  
标签:lfloor frac limits 题解 sum rfloor mu 采集 NOI2010

【NOI2010】能量采集 题解

谨纪念我的第一道手推出来的莫反题。

题目大意:已知 \(n\),\(m\),求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot \gcd(i,j)-1)\)。

首先变形一手:

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^m(2\cdot\gcd(i,j)-1)=2\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)-n\times m \]

然后我们只用求出中间那两个 \(\sum\) 就好了。

\[\begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d=1}^nd[\gcd(i,j)=d]\\ &=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\\ &=\sum\limits_{d=1}^nd\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{x|\gcd(i,j)}\mu(x)\\ &=\sum\limits_{d=1}^nd\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor} \mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor \end{aligned} \]

令 \(T=dx\),

\[\begin{aligned} \sum\limits_{d=1}^nd\sum\limits_{x=1}^{\lfloor\frac{n}{d}\rfloor} \mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor &=\sum\limits_{d=1}^nd\sum\limits_{T=1}^n\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor[d|T]\\ &=\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d=1}^nd\cdot\mu(\frac{T}{d})[d|T]\\ &=\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}d\cdot\mu(\frac{T}{d}) \end{aligned} \]

如何处理后面那个 \(\sum\),考虑狄利克雷卷积。不会的可以看我博客。

因为 \(\varphi*I=Id_1\),又因 \(I*\mu=\epsilon\),所以

\[\varphi=Id_1*\mu \]

注意到右边那个 \(\sum\) 其实就是 \(Id_1*\mu\),即 \(\varphi\)。

所以可化为:

\[\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}d\cdot\mu(\frac{T}{d})=\sum\limits_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\cdot\varphi(T) \]

很明显的整除分块,预处理 \(\varphi\) 的前缀和就好了。

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+5;

int n,m;
int cnt,pri[N],phi[N],mu[N],sum[N];
bool flg[N];

void init()
{
    mu[1]=1,phi[1]=1;
    for(int i=2;i<=N-5;i++)
    {
        if(!flg[i])
            pri[++cnt]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;j<=cnt&&pri[j]*i<=N-5;j++)
        {
            flg[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            mu[i*pri[j]]=-mu[i];
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
    for(int i=1;i<=N-5;i++)
        sum[i]=sum[i-1]+phi[i];
}

int work(int n,int m)
{
    if(n>m) swap(n,m);
    int res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        res+=(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    return res;
}

signed main()
{
    init();
    scanf("%lld%lld",&n,&m);
    printf("%lld\n",2*work(n,m)-n*m);
    return 0;
}

标签:lfloor,frac,limits,题解,sum,rfloor,mu,采集,NOI2010
From: https://www.cnblogs.com/holmes-wang/p/18212595

相关文章

  • 排查采集终端ota失败问题
    现象采集终端ota后发现版本号不对(版本号应变成v1.2.0)排查过程此问题是技术支持同事在客户现场安装时发现的,需要尽快解决;采集终端与智慧屏通过蓝牙连接通信,智慧屏将采集终端固件发送给采集终端。问题要不是智慧屏蓝牙程序问题,要不是采集终端程序问题。将智慧屏蓝牙程序回退到之......
  • 有哪些地图采集软件可以采集商家数据导出功能?
    1.国内商家采集寅甲地图数据采集软件寅甲地图数据采集软件一款多关键词多城市同时采集百度地图、360地图、高德地图、搜狗地图、腾讯地图、图吧地图、天地图商家、公司、店铺的手机、座机、地址、坐标等数据信息的软件。2.国外商家采集寅甲谷歌地图数据采集软件专为做外......
  • CF1973F Maximum GCD Sum Queries 题解
    题目链接点击打开链接题目解法首先想到枚举两个数列的$\gcd$,求最小代价两个数列的\(\gcd\)应该分别是\(a_1,b_1\)的因数或\(b_1,a_1\)的因数这样就把枚举范围缩小到了\(d(a_1)\timesd(b_1)\),这求最小代价需要\(O(n)\),不够快假设枚举的\(\gcd\)分别为\(x,y\)......
  • CF1909I Short Permutation Problem 题解
    这是一道*1900的黑。考虑枚举\(m\),将\(<\fracm2\)和\(\ge\fracm2\)的数分开讨论。考虑相邻两个数\(a,b\(a>b)\)分别在\(\fracm2\)的两侧,则有\(b\gem-a\)。考虑将所有数按某种方法从小到大排序,以\(\min(x,m-x)\)为第一关键字,\(-x\)为第二关键字,则排列中......
  • 【达梦问题解决】to_date转换之【文字与格式字符串不匹配】
    【问题描述】因为要转换的值中包含了不属于时间格式的字符(T,Z),这可能是数据迁移时时间参数设置不对导致的。具体没有进行考究【问题解决】使用DATE分隔符解决【手册链接】格式符解释实际分隔符的处理办法【自定义转换函数】这里的自定函数是不完善的,因为我的数......
  • 采集终端蓝牙指示灯莫名闪烁
    现象智慧屏和采集终端蓝牙还未连接,但蓝牙指示灯在闪烁;排查步骤问题原因有两种可能如下情况1:蓝牙指示灯在闪烁,说明有智慧屏连接了它;情况2:或者采集终端蓝牙固件有bug;情况1验证:将采集终端拿到电梯里,给采集终端供电,发现蓝牙指示灯不在闪烁,试验3次,结果都一样;情况1验证结果:确实有......
  • 采集数据产品描述有超链接///设置免运费后,达到免送标准,其他运费不显示///给产品详情页
    //产品描述有超链接,去掉functionremove_product_hyperlinks($content){if(is_product()){//确保只在产品页面上应用$content=preg_replace('/<ahref=".*?">(.*?)<\/a>/','$1',$content);}return$content;}add_......
  • CF1939D Big Persimmon 题解
    题目链接点击打开链接题目解法什么神仙题/jy先把\(a_i\)都\(\times2\),默认一开始先手比后手快\(1\)时间,可以避免两个人同时结束一个柿子的情况朴素的\(dp\)是显然的,令\(f_{l,r,det}\)表示当前剩下区间\([l,r]\)中的柿子,先手比后手快了\(det\)秒,先手最多能比后......
  • 充电桩——微信小程序,缴纳的1000元交易保障金,问题解答。
    1、小程序后台,申请退款保障金有一条不符合要求,无法退款。 2、咨询客服,能否退款然后再以公司名义缴纳保证金,等待回复:暂不支持对公转账,只能微信扫码支付缴纳哈。退保的话,支持退回对公账户。详情请查看小程序交易保证金管理规定https://developers.weixin.qq.com/miniprogram/de......
  • P5531 [CCO2019] Human Error 题解
    可能是一个比较劣的做法。但复杂度是对的。思路我们容易发现状态数非常的稀少。一个比较宽松的上限时\(3^{13}\)种状态由于每个点每走一步会吃掉一个棋子。所以实际的状态是远远达不到这个上限。那么我们可以直接设\(dp_{i,0/1,0/1}\)为在\(i\)状态下,目前是Justin......