FZU 1591 Coral的烦恼_weixin_30919429的博客-程序员宅基地

Problem Description

 

程序设计课的老师给Coral布置了一道题:用T(n)表示所有能整除n的正整数之和,对于给定的数字n,记S(n)=T(1)+T(2)+…+ T(n)。你的任务就是帮助Coral求出S(n)。

 Input

 

本题有多组输入数据,你必须处理到EOF为止。

每组数据输入仅一行一个整数n (1<=n<231)。

 

 Output

 

输出一行一个数字S(n)。


有种 O(N)的算法 for(i = 1; i <= N; i++) sum(i*(n/i));
意思就是 枚举每个 因子总共出现的次数乘以该因子 比如 在100 中 2会被计算 50次 3会被计算33次 那么 2*50 + 3*33就是 因子2和因子3在n=100时的总和

但是我们可以将复杂度简化到 sqrt(N);
对于给定的 N,记 sq = sqrt(N);
对于 1<= i < sq,计算
sum(i*(n/i)),这样得到了答案的一部分(对于小于 sq 的因子 i 乘以所有可能的个数,再加起来)。
那么 >= sq 的因子 j
呢?
我们可以统计自 j 到 N 的数中,某因子出现 1 次的数(肯定是连续的)的个数,出现 2 次的数(肯定是连续的)的个数,。。。。。。
比如
N = 12;sq = 3;
那么因子 1,2,3 招致的和就是 1* 12 + 2*6 + 3* 4 = 36。
自 4 到 12 ,该因子 出现 1 次的数是 7,8,9,10,11,12;和是 (7+ 12) * 6/2 = 57;
该因子出现 2 次的数是 5,6,和是 (5+6) * 2 = 22;
该因子出现 3 次的数是 4,和是 12。
那么出现 ii 次的数是 (N/(1+ii), N/ii]。
转自 http://218.245.3.161/2011/03/08/5687


#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <math.h> #include <stdio.h> #include <string.h> using namespace std; #define maxm 100010 #define maxn 1000110 int main() { int n; int i; __int64 ans=0; __int64 l,r; while(scanf("%d",&n)!=EOF){ ans=0; for(i=1;i*i<=n;i++){ l=n/(i+1)+1,r=n/i; if(l>i) ans+=(l+r)*(r-l+1)/2*i; ans+=(n/i)*i; } printf("%I64d\n",ans); } return 0; }

 

转载于:https://www.cnblogs.com/372465774y/p/3210811.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30919429/article/details/97789373

智能推荐

YARN 在快手的应用实践与技术演进之路_过往记忆的博客-程序员宅基地

本文是房孝敬老师主题为“yarn在快手应用实践与技术演进之路”的分享整理,内容包含yarn系统在快手的应用实践,遇到的问题以及相应的技术演进过程。讲师介绍:房孝敬,快手大数据架构团队调度方向负责人,目前负责快手公司Hadoop生态中调度、AI架构等子系统内核与周边子系统的研发,并推动在公司内的应用。2011年毕业于北京邮电大学,曾就职于阿里、腾讯。主要研究领域包括Docker云平台,分布式调度和计...

Angular15 利用ng2-file-upload实现文件上传_weixin_30653023的博客-程序员宅基地

待更新转载于:https://www.cnblogs.com/NeverCtrl-C/p/8279246.html

原生js写的贪吃蛇网页版游戏特效_weixin_33909059的博客-程序员宅基地

&lt;meta http-equiv="Content-Type" content="text/html; charset=utf-8"&gt;&lt;body&gt;&lt;title&gt;原生js写的贪吃蛇网页版游戏特效代码 demo by js.alixixi.com&lt;/title&gt;&lt;/body&gt;&lt;scri...

Packet for query is too large (4,544,730 > 4,194,304). You can change this value on the server by se..._花儿为何那样红的博客-程序员宅基地

修改 my.ini 加上 max_allowed_packet =6710886467108864=64M默认大小4194304 也就是4M修改完成之后要重启mysql服务,如果通过命令行修改就不用重启mysql服务。命令修改:设置为500Mmysql&gt; set global max_allowed_packet = 500*1024*1024;查看mysql的max_al...

javascript正则表达式_The butcher的博客-程序员宅基地

// 正则:// 正确的规则:// 字符的正则的规则,所以说,正则使用来操作字符串的 // 正则对字符串提供的三大功能: // 验证: reg.test(str) // 查询: str.search(reg) / str.match(reg) // 替换: str.replace(reg,newStr); // 注意:哪个方法...

(一)sklearn数据预处理_HawardScut的博客-程序员宅基地

from sklearn import preprocessingimport numpy as npX_train = np.array([[ 1., -1., 2.], [ 2., 0., 0.], [ 0., 1., -1.]])1、使得均值0,方差1X_scaled = preproce...

随便推点

python 股市 无风险套利_Python期货期权无风险套利监控升级版_weixin_39566914的博客-程序员宅基地

代码基于天勤量化平台,先贴出完整代码:#!/usr/bin/env python# -*- coding: utf-8 -*-#import asynciofrom tqsdk import TqApi, TqAuthfrom contextlib import closingfrom time import time# 创建API实例.api = TqApi(auth=TqAuth("天勤账号...

《算法导论》第2章 算法基础(插入排序、归并排序、复杂度计算)_神安羽白的博客-程序员宅基地

(最近在自己学习《算法导论》一本书,之前本来喜欢手写笔记,但是随即发现自己总是把笔记弄丢,所以打算做一个电子版的笔记)(另外书中用的都是伪代码,笔记中如果需要尝试的地方都是python代码)2.1 插入排序 基本思想:将待排序的数列看成两个部分(以从小到大为例),前一半是排序完成的,后一半是乱序的,对于乱序的第一个,开始和前一半里最大的数字、第二大的数字……依次比较,等到合适的位置就将它放进去。然后比对过的数字向后移动一位,相应的排序完成的长度加一,没有排序的减一。如:5 |...

Hadoop3.3新版本发布【整合了腾讯云】_about云的博客-程序员宅基地

问题导读1.Hadoop3.3支持JDK哪个版本?2.SCM是什么?3.YARN应用程序做了哪些改进?4.整合腾讯云实现了什么文件系统?1.支持ARM这是第一个支持ARM的版本。2.Pr...

SQL Server创建事务——锁_weixin_33836874的博客-程序员宅基地

参考地址:http://www.cnblogs.com/knowledgesea/p/3714417.html事务定义:事务是作为单个逻辑单元执行的一系列操作,它是一个不可分割的工作逻辑单元。它包含了一组数据库操作命令,这组命令要么全部执行,要么全部不执行。举个例子,我们经常用到的 ATM 存取款机,比如转账的时候,是先减去转出账户的金额,然后再在指定转入账户的金额加上转出的金额。如果...

AS中如何引用lib资源?_尹人入胜的博客-程序员宅基地

在eclipse中我们如果用so,则直接放在项目目录下的libs中即可,那么在Android Studio(AS)中加入要导入so,是不是也放在libs中就可以了呢?答案当然不是,AS的编译特点是基于gradle完成的,所以我们还要在项目目录中的app层级下的build.gradle中的android{}方法中加上以下配置:sourceSets { main {

树莓派tcp服务器性能,【树莓派3B+测评】TCP客户端&阻塞线程创建&取消_你的阿暖的博客-程序员宅基地

【树莓派3B+测评】TCP客户端&amp;阻塞线程创建&amp;取消[复制链接]本帖最后由 donatello1996 于 2018-12-19 09:30 编辑【树莓派3B+测评】TCP客户端&amp;阻塞线程创建&amp;取消在Linux系统中,TCP通信还有一个常用角色是客户端,像树莓派这种板子,经常充当从机角色连接电脑主机,在这种情况下,以客户端身份连接主机是比较易于理解且占用资源较少的做...