2818: Gcd

2818: Gcd

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 2170  Solved: 979

[Submit][Status][Discuss]

Description

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对.

Input

一个整数N

Output

如题

Sample Input

4

Sample Output

4

HINT

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

1<=N<=10^7

Source

湖北省队互测

题解:一个素数+欧拉函数题,其实就是先求出1-N的欧拉函数,然后枚举1-N之间的质数,然后简单加加就可以了

对了——每次加入的时候在乘2之后记得减1——因为有且仅有一种情况两个数字相同——那就是两个数字刚好等于那个质数,别的没了

 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
37      readln(n);m:=0;phi;ans:=0;
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);
41      readln;
42 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法模板——计算几何2(二维凸包——Andrew算法)

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

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

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

    HansBug
  • 1601: [Usaco2008 Oct]灌水

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

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

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

    HansBug
  • 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风骚,一时风光无二。相比于虚拟机来说,容器更轻,一台服务器上可以运行成百上千的容器,这意味着更为密集的计...

    SDNLAB
  • RNA-Seq数据用aspera高效批量下载(万事开头难)

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

    生信技能树

扫码关注云+社区

领取腾讯云代金券