# 2818: Gcd

## 2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 2170  Solved: 979

[Submit][Status][Discuss]

4

4

## HINT

hint 对于样例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

## Source

``` 1 /**************************************************************
2     Problem: 2818
3     User: HansBug
4     Language: Pascal
5     Result: Accepted
6     Time:1900 ms
7     Memory:156476 kb
8 ****************************************************************/
9
10 var
11    i,j,k,l,m,n:longint;ans:int64;
12    a,b:array[0..10000005] of longint;
13    c:array[0..10000005] of int64;
14 procedure phi;
15           var i,j:longint;
16           begin
17                m:=0;a[1]:=1;
18                for i:=2 to n do
19                    begin
20                         if a[i]=0 then
21                            begin
22                                 inc(m);
23                                 b[m]:=i;
24                                 a[i]:=i-1;
25                            end;
26                         for j:=1 to m do
27                             begin
28                                  if (i*b[j])>n then break;
29                                  if (i mod b[j])=0 then
30                                     a[i*b[j]]:=a[i]*b[j]
31                                  else
32                                      a[i*b[j]]:=a[i]*(b[j]-1);
33                             end
34                    end;
35           end;
36 begin
38      for i:=1 to n do c[i]:=c[i-1]+int64(a[i]);
39      for i:=1 to m do inc(ans,c[n div b[i]]*2-1);
40      writeln(ans);
42 end.```

0 条评论

• ### 算法模板——计算几何2（二维凸包——Andrew算法）

实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298） 很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反...

• ### 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 M...

• ### 1601: [Usaco2008 Oct]灌水

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

• ### 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 Time Limit: 10 Sec  Memory Limit: 64 M...

• ### Qt学习前言

完全基于Linux真正成长起来的公司仍然寥寥无几，而奇趣试图在开源里找到一条独特的发展之路。

• ### 马蜂窝容器化平台前端赋能实践

最初当我向公司的前端同学「安利」容器技术的时候，很多人都会说：「容器？这不是用在后端的技术吗？我不懂啊，而且前端开发用不上吧。」

• ### 严选 | ELK Stack 选书指南

非针对ELK Stack的书，是搜索引擎原理的书，Elasticsearch也是开源搜索引擎的一种，原理通用。

• ### Leetcode: Best Time to Buy and Sell Stock

题目： Say you have an array for which the ith element is the price of a given st...

• ### SDNLAB技术分享（十五）：容器网络大观

一、容器网络概述 容器这一两年火的不行，可以说是独领IT风骚，一时风光无二。相比于虚拟机来说，容器更轻，一台服务器上可以运行成百上千的容器，这意味着更为密集的计...

• ### RNA-Seq数据用aspera高效批量下载（万事开头难）

由于是EBI数据库，用wget下载速度太慢，Jimmy大神强烈建议用aspera工具下载，于是参考生信技能树教程代码，首先需要熟悉GEO和SRA数据库：