在线编程在线课堂在线测评Anycodes在线编程

编程论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

How to use bs4??
本帖最后由 carry0987 于
Double Queue 问题描述 : The new founded Balkan Investment Group Bank (
John 问题描述 : Little John is playing very funny game
linux-command Linux命令大全搜索工具,内容包含Linux命令
Coati 是一款跨平台的代码查看工具,适用于 C/C++ 和 Java。商业软件。特性:1. 索引
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
全平台视频监控,支持安卓苹果以及pcweb,支持海康大华等主流dvr,全部源码以及文档 单聊、群聊、商
如何访问类的私有属性? 下面以 TPathData 为例,
问题:从 XE4 以来,Firemonkey 曲线绘图在移动平台不平滑的问题一直令人诟病,提交到官方的 QC 也是族繁不及备载,官方似乎有意的
操作数据库(RODBC)   odbcConnect(dsn, uid="", p
数据模式:mode函数显示任何对象的模式。常见的单个的
系统可承载海量并发,消息收发确认机制 保障消息必达 系统采用动态智
RabbitMQ与PHP(一) 项
Iease团队扩编预备中,盼望能有Ruby或者java工程师加盟。全职兼职都可以。有爱好的伴侣请与我接洽。 邮件:i
ruby 怎么设置装备摆设GTK2,求教指导下!
#include #include #include #include using namespace std; int main() {
标题如图所示: 有n盏灯,编号1~n。一开端灯都是关着的
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
成熟的消息收发确认机制,支持万人大群 支持开发自定义的消息sdk接口,扩展性超强 支持单/
1. 注意列表和集合的区别 set 列表表现形式: list_1
Ajax   Ajax即“Asynchronous Javascript And
大师好,我比来在做布谷鸟优
分辨提取A和B图像Harris角点,接下来须要对

[HDU杭电] HDU 1215 七夕节-数论-[解题报告] c-sharp

[复制链接]
发表于 2016-3-26 22:17:52 | 显示全部楼层 |阅读模式
七夕节


问题描述 :
七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"
人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下:

HDU 1215 七夕节-数论-[解题报告] c-sharp

HDU 1215 七夕节-数论-[解题报告] c-sharp
数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
你想知道你的另一半吗?
输入:
输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).
输出:
对于每组测试数据,请输出一个代表输入数据N的另一半的编号.
样例输入:

  1. 3
  2. 2
  3. 10
  4. 20
复制代码
样例输出:

  1. 1
  2. 8
  3. 22
复制代码
http://acm.hdu.edu.cn/showproblem.php?pid=1215 解题思路:我是用到了数论上的一个求因子和的公式来求的。 若n = p1^e1 * p2^e2 * ……*p3^e3(任何一个数都可以分解成素数乘积) 则n的因子个数为  (1+e1)(1+e2)……(1+e3) n的各个因子的和为(1+p1+p1^2+……+p1^e1)(1+p2+p2^2+……+p2^e2)……(1+p3+p3^2+……+p3^e3)
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <string.h>
  4. #define N 500001
  5. __int64 p[5000];
  6. int hash[N];
  7. bool visited[N];

  8. void GetPrime(int Max)
  9. {
  10.         int i,sqr,j,len = 0;
  11.         memset(visited,0,sizeof(visited));
  12.         sqr = (int)sqrt(N*1.0);
  13.         for (i=2;i<=sqr;i++)
  14.         {
  15.                 if(visited[i])
  16.                         continue;
  17.                 for (j=i*i;j<N;j+=i)
  18.                         if(!visited[j])
  19.                                 visited[j] = 1;
  20.         }
  21. }

  22. int main()
  23. {
  24.     __int64 i, ans, n, m, temp,k,len = 0;
  25.         int test;
  26. /*
  27.         freopen("d://2.txt","r",stdin);
  28. */
  29.         GetPrime(N);
  30.         for(i=2;i<N;i++)
  31.                 if(!visited[i])
  32.                         hash[len++] = i;

  33.         scanf("%d",&test);
  34.    
  35.     while (test--)
  36.     {      
  37.                 scanf("%I64d", &n);
  38.         m = n;
  39.                 ans = 1;
  40.         for (i=0;hash[i]<=m&&i<len;i++)
  41.         {
  42.                         if(m==1)
  43.                                 break;
  44.                         if(m%hash[i]==0)
  45.                         {
  46.                                 temp = 1;
  47.                                 k = 1;
  48.                                 while (m%hash[i]==0)
  49.                                 {
  50.                                         m/=hash[i];
  51.                                         temp = temp+k*hash[i];
  52.                                         k = k*hash[i];
  53.                                 }
  54.                                 ans*=temp;
  55.                         }
  56.         }
  57.                 printf("%I64d/n",ans-n);
  58.     }
  59.         return 0;
  60. }
复制代码
网上看了别人的代码,别人直接打表,效率比我上面的高非常多,93ms,自己的跑了400多ms,效率啊,还得继续努力。
  1. #include<iostream>
  2. using namespace std;
  3. long a[500000];
  4. int main()
  5. {
  6.         long i,n,j,r,k;
  7.         scanf("%ld",&n);
  8.         {
  9.                 for(i=2;i<500001;i++)
  10.                         a[i]=1;
  11.                 a[0]=0;
  12.                 a[1]=0;
  13.                 for(i=2;i<=250000;i++)
  14.                 {
  15.                         for(j=i+i;j<=500000;j+=i) //这里凡是i的倍数的a[j]都加上 i 。//
  16.                         {
  17.                                 a[j]+=i;      
  18.                         }
  19.                 }
  20.                 for(r=0;r<n;r++)
  21.                 {
  22.                         scanf("%ld",&k);
  23.                         printf("%ld/n",a[k]);
  24.                 }  
  25.         }
  26.         return 0;
  27. }
复制代码
在线编程(http://www.anycodes.cn)&编程论坛(http://www.52exe.cn)感谢您的支持!
回复

使用道具 举报

发布主题 上个主题 下个主题 快速回复 返回列表 官方QQ群
在线客服
客 服 中 心
群 机 器 人
网站二维码
收 起 客 服

QQ|Archiver|手机版|小黑屋|Anycodes ( ICP14002806Anycodes在线编程

GMT+8, 2018-11-22 01:12 , Processed in 2.173934 second(s), 71 queries .

Powered by Anycodes

© 2001-2013 吉林市群龙科技有限公司 Inc.

快速回复 返回顶部 返回列表