P1390 公约数的和

题目描述

有一天,TIBBAR和LXL比赛谁先算出1~N这N个数中每任意两个不同的数的最大公约数的和。LXL还在敲一个复杂而冗长的程序,争取能在100s内出解。而TIBBAR则直接想1s秒过而获得完胜,请你帮他完成这个任务。

输入输出格式

输入格式:

共一行,一个正整数N。

输出格式:

共一行,一个数,为1~N这N个数中每任意两个不同的数的最大公约数的和。

输入输出样例

输入样例#1:

10
输出样例#1:

67

说明

对于40%的数据,2≤N≤2000.

对于100%的数据,2≤N≤2000000.

这个题怪好

不妨设f(n) = (1,n) + (2,n) + (3,n) + (4,n) + ... + (n-2,n) + (n-1,n)

则答案为f(2) + f(3) + f(4) + ... + f(n - 1) + f(n)

对于任意数i,若(i, n) = k,  则(i/k, n/k) = 1,不难得到

f(n) = Σ(i | n)phi(n/i) * i

对于每个i,枚举其倍数n即可

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
inline void read(long long &x){x = ;char ch = getchar();char c = ch;while(ch > '' || ch < '')c = ch, ch = getchar();while(ch >= '' && ch <= '')x = x * + ch - '', ch = getchar();}
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a < b ? a : b;}
inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;} const int INF = 0x3f3f3f3f;
const int MAXN = + ; long long n;
long long ans; long long prime[MAXN],phi[MAXN],cnt;
bool bp[MAXN]; inline void makephi()
{
phi[] = ;
for(register long long i = ;i <= n;++ i)
{
if(!bp[i])
prime[++cnt] = i, phi[i] = i - ; for(register long long j = ;j <= cnt;++ j)
{
if(i * prime[j] > n)break;
bp[i* prime[j]] = ;
if(i % prime[j] == )
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - );
}
}
} long long f[MAXN]; int main()
{
read(n);
makephi();
for(register int i = ;i <= n;i ++)
{
for(register int j = i * ;j <= n;j += i)
{
f[j] += phi[j / i] * i;
}
}
for(register int i = ;i <= n;++ i)
ans += f[i];
printf("%lld", ans);
return ;
}

最新文章

  1. java占位符应用
  2. HDU 4937 Lucky Number(2014 Multi-University Training Contest 7)
  3. php Memcache
  4. ASP.NET- 执行SQL超时的解决方案
  5. json数组对象和对象数组(转)
  6. @@ROWCOUNT 含义
  7. .htaccess 保护文件夹
  8. OSX MacVim + vim-lldb配置和使用心得
  9. Python3 re模块(正则表达式)
  10. 【unix网络编程第三版】阅读笔记(五):I/O复用:select和poll函数
  11. java造成内存泄露原因
  12. 开源自己写的Library到github,让别人或自己的项目依赖
  13. P4478 [BJWC2018]上学路线
  14. java中定时执行任务
  15. Linux基础命令---文本统计wc
  16. linux内核中的LPM是什么?
  17. Linux的vi编辑器笔记
  18. java中enum的应用
  19. jquery.peity.js简介
  20. 使用Eclipse对FFmpeg进行调试

热门文章

  1. php数据结构课程---6、常见排序有哪些
  2. 杂项-公司:Facebook
  3. System.Web.Mvc.PartialViewResult.cs
  4. 隐藏/显示jeecg-boot 后端管理页面的右侧的系统设置
  5. 并查集 (poj 1611 The Suspects)
  6. 在 Node.js 中引入模块:你所需要知道的一切都在这里
  7. 重装一次CM的坑爹记录
  8. python3.6.4安装错误0x80072efd
  9. PostgreSQL DISTINCT ON
  10. 2018-8-10-dotnet-从入门到放弃的-500-篇文章合集