注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

质因数分解应用  

2009-05-25 15:12:40|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

通宵教室
Acceteped : 65    Submit : 311 
Time Limit : 1000 MS   Memory Limit : 65536 KB

Description
      高校扩招,教室一度变得很紧张。学生白天上自习的地方较少,晚上教室又闲置着,怎样才能充分利用教学资源,扩大学生自习时空呢?通宵教室解决学生自习空间有限和教学资源不充分利用的问题。开放通宵教室促进了学生学习观念的转变,以前课堂内外基本上是听老师安排,现在是学生自觉在学习。晚上学习效率高、生理调节能力强的学生已经尝到了甜头。好学、考研、辅修、创作的学生又有了一片新的学习时空。
      但是通宵教室对传统的学生管理工作带来了一系列的问题。如果通宵教室的利用率不高的话,将教室的所有灯都打开,还会极大地浪费能源。
      现在学校对通宵教室灯光使用做一个新的尝试。假设有N个人使用通宵教室,教室里有N盏灯,每个人和每盏灯都有一个编号。开始所有的灯都没打开,第一个人进教室将所有的灯都打开,第二个人将所有的偶数号的灯都关掉,第三个人对所有3的倍数的灯进行如下操作:如果灯开着,就将它关掉,如果灯关着,就将它打开,……,第i个人对所有i的倍数的灯进行如下操作:如果灯开着,就将它关掉,如果灯关着,就将它打开,重复这样的过程,一直到第N个人完成这样的操作。
      现在,教室管理员向你求助,他希望知道,完成这样的过程后,教室里开着的灯还有多少盏?
Input
      有多组测试数据。第一行是一个正整数T(1<=T<=10000),表示有多少组测试数据。以下有T行,每行一个测试数据,包含唯一的一个正整数N(1 <= n < 232)。
Output
      对于每个测试数据,输出一行包含唯一的一个整数:表示完成这样的过程后,教室里开着的灯的盏数。
Sample Input 
2
1
2
Sample Output 
1
1

主要思想:
1.由题目可知任何一盏灯最后打开的条件是对其操作奇数次,关闭的条件是对其操作偶数次。而能够控制这盏灯的人的编号一定是这盏灯编号的因子。所以题目就转换为根据每盏灯编号的因子个数来判断灯为亮或暗。但是由于灯的个数可以很大,如果从1到n算出每个数因子的个数是不可能的。
2.现在我们根据质因数分解来找出其中的规律。每个合数都可以写成几个质数相乘的形式。所以对n进行质因数分解后n=(2^X)*(3^Y)*(5^Z)*……,所以总的因子个数为(X+1)(Y+1)(Z+1)……,只有(X+1)(Y+1)(Z+1)……为奇数的时候n最后才是亮的,所以X,Y,Z都是偶数。所以可以得出n一定是完全平方数。这时题目已经转换为求n前面完全平方数的个数。所以最后的答案应该是floor(sqrt(n))。

代码如下:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int t,result;
    double n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lf",&n);
        result=(int)sqrt(n);
        printf("%d\n",result);
    }
    return 0;
}

 

  评论这张
 
阅读(457)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017