首页 > 其他分享 >题解:疯狂lcm

题解:疯狂lcm

时间:2023-11-09 18:58:34浏览次数:40  
标签:frac gcd 题解 sum 疯狂 varphi mid lcm times

%你赛打到一半来写个题解

link:疯狂lcm

题意,求:

\[\sum_{i=1}^{n}lcm(i,n) \]

不多说废话,直接开推:

\[\begin{aligned} &=n\sum_{i=1}^{n}\frac{i}{gcd(i,n)}\\ &=n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[gcd(i,n)=d]\\ &=n\sum_{d\mid n}\sum_{i=1}^{n}\frac{i}{d}[gcd(\frac{i}{d},\frac{n}{d})=1]\\ &=n\sum_{d\mid n}\sum_{i=1}^{\frac{n}{d}}i[gcd(i,\frac{n}{d})=1]\\ \end{aligned} \]

我们发现这个 \(\frac{n}{d}\) 实际上还是枚举的 \(d\),那我们来直接替换:

\[n\sum_{d\mid n}\sum_{i=1}^{d}i[gcd(i,d)=1] \]

那么后边这个 \(\sum_{i=1}^{d}i[gcd(i,d)=1]\) 实际上就是小于 \(d\) 且与 \(d\) 互质的数的和,这玩意就等于 \(\frac{\varphi(n)\times n}{2}\),证明如下:

由于更相减损法 \(gcd(n,x)=gcd(n,n-x)\) 可知,所有与 \(n\) 互质的数都是成对出现的,每一对的和为 \(n\),一共有 \(\frac{\varphi(n)}{2}\) 对,那么和为 \(\frac{\varphi(n)\times n}{2}\),当然要在 \(n>1\) 的条件下满足。

那么原式即变为:

\[n\sum_{d\mid n}\frac{\varphi(d)\times d}{2} \]

但是如果 \(d=1\) 上式变为 \(0\),就不成立了,因此 \(d=1\) 的时候特判一下就好。

容易发现这是一个 \(\Theta(\sqrt{n})\) 的算法,优化一下,设 \(f(n)=\sum_{d\mid n}\varphi(d)\times d\),也就是 \(1*(\varphi(n)\times n)\),它显然是个积性函数,那可以考虑用个筛子筛一下,很容易将复杂度降到 \(\log n\) 级别。

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,T;
int prim[N],phi[N],f[N];
void init(){
    phi[1]=1;
    for(int i=2;i<=N;++i){
        if(!phi[i]) prim[++prim[0]]=i,phi[i]=i-1;
        for(int j=1;j<=prim[0]&&i*prim[j]<=N;++j){
            if(!(i%prim[j])){
                phi[i*prim[j]]=prim[j]*phi[i];
                break;
            }else phi[i*prim[j]]=(prim[j]-1)*phi[i];
        }
    }
    for(int i=1;i<=N;++i)
        for(int j=i;j<=N;j+=i) f[j]+=(i==1)?1:(phi[i]*i/2);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    init();
    cin>>T;
    while(T-->0){
        cin>>n;
        cout<<f[n]*n<<'\n';
    }
    return 0;  
}

标签:frac,gcd,题解,sum,疯狂,varphi,mid,lcm,times
From: https://www.cnblogs.com/shen666zxcmt/p/17822530.html

相关文章

  • 小程序性能优化之避免"全局疯狂"
    大家好,今天我们来聊一聊小程序性能优化的小窍门——避免过度使用全局变量。你知道吗?在程序的世界里,有一种特别的"魔法",叫做"全局变量"。它就像一个超级大宝库,无论你需要什么,都可以从中取出。但是,这个宝库也有一个坏处,就是当你用得太多时,程序就会变得慢吞吞的,就像一个戴着厚重帽子的......
  • KubeEdge部署 完美运行 附问题解决方法
    云端部署环境准备一、部署前工作(k8s、docker安装及配置、初始化集群、golang安装、keadm安装)配置网络参数cat>>/etc/hosts<<EOF#GitHubStart52.74.223.119github.com192.30.253.119gist.github.com54.169.195.247api.github.com185.199.111.153assets-cdn.gith......
  • linux/docker 版 Sql Server新建的数据库插入中文乱码问题解决方案
    SqlServer插入遇到乱码原因:在英文系统中,SqlServer默认排序规则为英文字典顺序解决方案一:容器版SqlServer,在创建容器时,可以加上环境变量-eMSSQL_COLLATION=Chinese_PRC_CI_AS-eTZ=Asia/Shanghai 把排序规则设为中文字典顺序并忽略大小写区分重音,时区设置为上海,不然......
  • 关于昨天疯狂报错的问题的解决
    问题描述昨天就一直hbase报错,进入zookeeper的zkCli.sh报错,一直进不去,给我整的挺崩溃的其实;问题解决今天再次打开虚拟机发现,我的FinalShell里面,这里的配置:自从上次改正本地的hosts文件之后,就一直三个ip地址都是192.168.88.151,然后昨天总的来说,就是一直在一台虚拟机上运行,没有......
  • CSP-S 2023 T1 题解
    CSP-S2023T1题解很简单,我们只需要暴力枚举五位密码,每次判断拨一个齿轮和两个齿轮能达到的状态数,如果等于\(n\),答案\(+1\)。时间复杂度\(O(10^5\times5n)\)。code#include<iostream>#include<algorithm>#include<cmath>#include<cstring>usingnamespacestd;......
  • P4069 题解
    简要题意给定一棵\(n\)个点的树,树有边权。对每个点维护一个集合\(S_u\),一开始集合均包含整数\(123456789123456789\)。设\({\rmdis}_{a,b}\)为树上两点\(a\),\(b\)的距离。共\(m\)次操作,分为如下两种:stab:设\(f\)为\(s\),\(t\)路径上的点集,对与\(\forall......
  • 上序问题解决补充(1)
    我发现好像只在idea里面整插件是不可以的你还需要下一个wampSERVER然后吧!他这个东西需要在法国官网下载,很他娘的慢,显示下载时间需要一天想不到吧我找到了中文站Wampserver3.3.064位官方版下载-WampServer中文站噔噔噔噔,闪亮登场......
  • cf908(div2)题解(补题)
    纪念这次div2让我上绿名,但还是有点遗憾,差一点就可以过三题超神了比赛链接cf908div2A这题是个骗人题,整个比赛会停下来就是一个人赢够了回合数,那么在谁这停下来就是谁赢了整个比赛,不用管每回合赢得规则。#include<iostream>usingnamespacestd;#include<string>intmain(){......
  • Qt - QWidget::setGeometry()不生效问题解决方案
    开发过程中经常碰到setGeometry()不生效的问题,发现只要在setGeometry()之前调用一下show()或者setVisible(true)就可以了!问题就出在setVisible(true)!!!setVisible()会判断当前控件的WA_WState_Created属性,意思就是看看控件是否已经创建了window,如果为没有创建,就调用create()方......
  • 第三方组件及计算属性传参的问题解决方式
    1.前言唉,好想玩滋嘣。2.计算属性直接传参接收不到表格数据某一列需要用的计算属性时,模板中使用计算属性fullName就会直接调用fullName函数,而在模板中fullName(item)相当于fullName()(item),此处为函数柯里化。<el-table-columnlabel="名称"align="center"min-width=......