洛谷P1390 公约数的和 [2017年6月计划 数论12]
2024-09-06 13:36:42
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 ;
}
最新文章
- java占位符应用
- HDU 4937 Lucky Number(2014 Multi-University Training Contest 7)
- php Memcache
- ASP.NET- 执行SQL超时的解决方案
- json数组对象和对象数组(转)
- @@ROWCOUNT 含义
- .htaccess 保护文件夹
- OSX MacVim + vim-lldb配置和使用心得
- Python3 re模块(正则表达式)
- 【unix网络编程第三版】阅读笔记(五):I/O复用:select和poll函数
- java造成内存泄露原因
- 开源自己写的Library到github,让别人或自己的项目依赖
- P4478 [BJWC2018]上学路线
- java中定时执行任务
- Linux基础命令---文本统计wc
- linux内核中的LPM是什么?
- Linux的vi编辑器笔记
- java中enum的应用
- jquery.peity.js简介
- 使用Eclipse对FFmpeg进行调试
热门文章
- php数据结构课程---6、常见排序有哪些
- 杂项-公司:Facebook
- System.Web.Mvc.PartialViewResult.cs
- 隐藏/显示jeecg-boot 后端管理页面的右侧的系统设置
- 并查集 (poj 1611 The Suspects)
- 在 Node.js 中引入模块:你所需要知道的一切都在这里
- 重装一次CM的坑爹记录
- python3.6.4安装错误0x80072efd
- PostgreSQL DISTINCT ON
- 2018-8-10-dotnet-从入门到放弃的-500-篇文章合集