正解:欧拉函数

解题报告:

传送门$QwQ$

首先显然十分套路地变下形是趴

$\begin{align*}&=\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)\\&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^{min(i,j)} [gcd(i,j)==d]\cdot d\\&=\sum_{d=1}^{n}d\cdot \sum_{i=1}^n\sum_{j=1}^n [gcd(i,j)==d]\\\end{align*}$

然后就欧拉函数做呗?直接戳我简要总结里常见套路第一条,就能$O(n)$做了$QwQ$

(说下昂,这题里其实是无序的,所以最后用$phi$的时候就可以直接$i\cdot \phi(i)$鸭$QwQ$

其实本来还有一种方法的但因为某不便透露的原因被删了$kk$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define sc second
#define gc getchar()
#define mp make_pair
#define int long long
#define P pair<int,int>
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=+;
int n,phi[N],sum[N],pr[N],pr_cnt,as;
bool is_pr[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void pre()
{
phi[]=;
rp(i,,N-)
{
if(!is_pr[i])pr[++pr_cnt]=i,phi[i]=i-;;sum[i]=sum[i-]+phi[i];
rp(j,,pr_cnt)
{
if(pr[j]*i>N-)break;;is_pr[pr[j]*i]=;
if(!(i%pr[j])){phi[i*pr[j]]=phi[i]*pr[j];break;}
phi[i*pr[j]]=phi[i]*phi[pr[j]];
}
}
} signed main()
{
//freopen("1390.in","r",stdin);freopen("1390.out","w",stdout);
pre();n=read();rp(i,,n/)as+=i*sum[n/i];
printf("%lld\n",as);
return ;
}

最新文章

  1. C++构造函数2
  2. 【代码笔记】iOS-下拉选项cell
  3. js jQuery中文字符串比较
  4. winform的常用公共控件和常用属性
  5. ZJOI2015 一试。
  6. 快速使用node.js进行web开发
  7. dedecms 列表页 list 判断flag给定指定样式 (本地测试有效)
  8. iOS --- 取整数
  9. CodeFirst-数据迁移-Migration
  10. pfSense软路由防火墙
  11. flask 上传文件
  12. include指令和include动作
  13. freemarker之数组(十八)
  14. go语言 nsq源码解读四 nsqlookupd源码options.go、context.go和wait_group_wrapper.go
  15. KnockOut 绑定之foreach绑定
  16. SSM框架中,controller的action返回参数给vue.js
  17. 在线批量将gps经纬度坐标转换为百度经纬度坐标
  18. 通过注解实现一个简易的Spring mvc框架
  19. python 小笔记
  20. 对于读txt文件一点总结

热门文章

  1. mysql把一个表的字段update成另一个表的字段根据id
  2. web移动开发小贴士
  3. php 位运算 3&lt;&lt;2;
  4. 3、.net core 部署到IIS
  5. 1、Ubuntu 16.04 安装.net core
  6. &quot;?:&quot;在正则表达式中什么意思
  7. css模仿ipad的日历
  8. Python--day24--单继承关键字super
  9. netstat 显示当前网络连接的统计信息
  10. centos7.0 可以访问HTML文件,不能访问PHP文件,因为php-fpm没有扩展包