JZOJ 3509. 【NOIP2013模拟11.5B组】倒霉的小C

traveller-ly 2018-07-19 原文

JZOJ 3509. 【NOIP2013模拟11.5B组】倒霉的小C

Description

小G最近迷上了岛国动漫《Angel Beats》，她为了画出一个更霸气的Angel Beats的logo，想了如下办法：

从（0，0）开始，画到（n，1），再从（n，1），画到（2*n，-1），再到（3*n，2），再到（4*n，-2），依此类推，即每次画出一个（n，(-1)^(i+1)*i）的向量，一共画出n个这样的向量。现在小G想让小C求出这个图形穿过了多少格点（坐标都是整数）。

由于小C想要认真地听他的数学课并且想自己在接力赛中因RP暴光而发生接力棒传错这类的糗事，所以这个问题就交给你啦。小G说，如果连你也解决不好，就把你的RP也吸光。

 

Input

输入文件中仅一行为一个整数n。

Output

输出文件中仅一行为一个数，表示穿过的格点数。
 

Sample Input

4

Sample Output

9
 
做法：

通过简单观察可以发现，每次画出向量（n，i）经过的格点个数为gcd(i，n)，那么答案就等于Ans=1+

 

 

直接求解的时间复杂度是O(n)的。

那么Ans=1+

 

其中d为n的约数。fai(n)表示1～n中与n互质的数的个数。通过这样的变形，我们就可以得到时间复杂度为O(C*sqrt(n))的算法，C为n的约数个数。

 

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <string>
 4 #include <cstring>
 5 #include <cmath>
 6 #define LL long long
 7 using namespace std;
 8 LL n, ans, k;
 9 
10 LL phi(LL x)
11 {
12     LL k = x;
13     for (int i = 2; x > 1; i++)
14         if (x % i == 0)
15         {
16             k -= k / i;
17             while (x % i == 0)    x /= i;    
18         }
19     return k;
20 }
21 
22 int main()
23 {
24     freopen("beats.in", "r", stdin);
25     freopen("beats.out", "w", stdout);
26     cin >> n;
27     int p = sqrt(n);
28     for (int i = 1; i <= p; i++)
29         if (n % i == 0)
30         {
31             k = i;
32             ans += k * phi(n / k);
33             if (k != n / k)    k = n / i, ans += k * phi(n / k);
34         }
35     cout << ans + 1;
36     return 0;
37 }

View Code

 

 

发表于 2018-07-19 21:42 执迷于沿途风景的旅人 阅读(…) 评论(…) 编辑 收藏

 

版权声明：本文为traveller-ly原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/traveller-ly/p/9338603.html

JZOJ 3509. 【NOIP2013模拟11.5B组】倒霉的小C的更多相关文章

  1. JZOJ 3385. 【NOIP2013模拟】黑魔法师之门

    JZOJ 3385. 【NOIP2013模拟】黑魔法师之门 3385. 【NOIP2013模拟】黑魔法师之门  […]...

  2. JZOJ 3223. 【HBOI2013】Ede的新背包问题

    JZOJ 3223. 【HBOI2013】Ede的新背包问题 3223. 【HBOI2013】Ede的新背包问 […]...

  3. JZOJ 1264. 乱头发节

    JZOJ 1264. 乱头发节 1264. 乱头发节(badhair.pas/c/cpp) (File IO) […]...

  4. JZOJ 1266. 玉米田

    JZOJ 1266. 玉米田 1266. 玉米田(cowfood.pas/c/cpp) (File IO):  […]...

  5. JZOJ 3382. 【NOIP2013模拟】七夕祭 (Standard IO)

    JZOJ 3382. 【NOIP2013模拟】七夕祭 (Standard IO) 3382. 【NOIP201 […]...

  6. JZOJ 2136. 【GDKOI2004】汉诺塔

    JZOJ 2136. 【GDKOI2004】汉诺塔 2136. 【GDKOI2004】汉诺塔 (Standar […]...

  7. JZOJ 3462. 【NOIP2013模拟联考5】休息(rest)

    JZOJ 3462. 【NOIP2013模拟联考5】休息(rest) 3462. 【NOIP2013模拟联考5 […]...

  8. JZOJ 4269. 【NOIP2015模拟10.27】挑竹签

    JZOJ 4269. 【NOIP2015模拟10.27】挑竹签 4269. 【NOIP2015模拟10.27】 […]...

随机推荐

  1. 做优秀产品经理所需的7种素质

    产品经理现在貌似一个很常见的IT工种，不过它是一个对个人综合素质要求非常高的职位，人称“产品灵魂的设计师”。有 […]...

  2. jquery click()方法模拟点击事件对a标签不生效的解决办法

    jquery click()方法模拟点击事件对a标签不生效的解决办法 阅读数：8971 <a href= […]...

  3. 微信公众平台开发教程（三） 基础框架搭建

    结合原理，详细介绍微信公众账号开发框架的搭建，包括Http请求、请求分发、处理以及响应。针对微信公众账号开发， […]...

  4. SAP ABAP: 把内表数据以excel或csv格式，通过前台或者后台的方式上传至FTP服务器

    今天接到一个FTP的需求，就是每天晚上把当天某个报表的数据自动保存excel上传到FTP服务器。 SAP已经有 […]...

  5. CSS3 — 弹性盒

    新版弹性盒 兼容到IE10及以上 flex小游戏 display: flex; 设置为弹性盒（父元素添加） f […]...

  6. raft协议

    一、Raft一致性算法 　　Eureka：Peer To Peer，每个节点的地位都是均等的，每个节点都可以接 […]...

  7. 开放下载 | 《Knative 云原生应用开发指南》开启云原生时代 Serverless 之门

    点击下载《Knative 云原生应用开发指南》 自 2018 年 Knative 项目开源后，就得到了广大开发 […]...

  8. PCI学习及编程访问PCI总线

     　PCI总线推出以来，以其独有的特性受到众多厂商的青睐，已经成为计算机扩展总线的主流。目前，国内的许多技术人 […]...

热门专题

缘从心开始
横向循环输出
基于Teigha.Net实现CAD到SHP的转换方案
简单介绍和使用问题小结
ANOVA-方差分析和单尾方差分析
Java8中的Stream
关于RESTful的理解
移动web开发
分享一个让我进入阿里中间件的个人项目
学习web前端之神器sublime
设置教程lightliliang
文本表
国内网页设计网站网址大全
交易所频频跑路？Baccarat去中心化交易平台助力资金安全
Http之状态码
【Java入门提高篇】Day26
病毒警告提示网站有病毒木马的解除方法Prolove
越狱和PDF插件的安装
改进的蝴蝶算法的详细介绍
python常用的内置模块
电容式触摸屏原理
展开目录

目录导航