频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
1283.山师好男友(开关灯问题)
2016-12-20 09:28:00         来源:一步一步走  
收藏   我要投稿

Description

川川想给他的女朋友一些惊喜,于是他准备了好多彩灯,他的女朋友十分感动,然后让川川这样做:如果她走到了第2盏彩灯处,那么川川就要改变所有2的倍数的灯的状态(灯有两种状态,开着的和关着的),假如一开始所有灯都是关着的,那么川川就要打开第2盏,第4盏,第6盏…,同样的道理,假如她走到的第三盏灯的位置,那么川川就要改变第3盏,第6盏,第9盏…的状态。

现在一开始所有的灯都是关着的,一共有N盏灯,川川从第2盏灯走到了第N盏灯,请问从第A盏灯跟第B盏灯之间(包含AB两盏),有多少彩灯是开着的?

Input

三个数,N,A,B(A,B,N<10^6)

Output

第A盏灯跟第B盏灯之间(包含AB)开着的灯的数目

Sample Input

5 1 3

Sample Output

2

思路:可以看出,被按了奇数次数的灯最后是开着的,而被按了偶数次数的灯最后是关着的。而如果一个数有偶数个因子那就会被按偶数次,如果有奇数个因子就会被按奇数次。这就会涉及到质因子分解定理,即任何正数都能被分解成多个质数的幂次乘积的形式

如:

14=2*7

50=2*5^2

100=2^2*5^2

也就是N=(p[1]^e[1])(p[2]^e[2])……(p[k]^e[k]),其中p[i]是质数,e[i]是p[i]的幂次。而由这个公式我们又可以导出一个数有多少个因子的计算公式:FactorNumber(N)=(e[1]+1)(e[2]+1)……(e[k]+1)。

那么什么条件下满足FactorNumber(N)是奇数呢?显然必须所有的e[1],e[2],……,e[k]都必须是偶数,这样才能保证e[i]+1是奇数,结果乘积才能是奇数。而由于e[1],e[2],……,e[k]都是偶数,那么N一定是一个完全平方数(因为sqrt(N)=(p[1]^(e[1]/2))(p[2]^(e[2]/2))……*(p[k]^(e[k]/2))是整数) 。回到按灯泡的问题上来,1~100中完全平方数有1,4,9,16,25,36,49,64,81,100这10个数,也就是说最后只有编号为这10个数的灯是亮着的。

世界杯外围投注官网 include <cmath>
世界杯外围投注官网 include <iostream>
世界杯外围投注官网 include <algorithm>
using namespace std;
int n, a, b, s;
int main ()
{
    while (cin >> n >> a >> b)
    {
        if (a > b)
            swap(a,b);
        s = 0;
        for (double i=a; i<=b; ++i)
        {
            double t = sqrt (i);
            if (t - (int)t)
                s++;
        }
        cout << s << endl;
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
上一篇:栈操作的问题
下一篇:C++读取硬盘序列号
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑--致力于做实用的IT技术学习网站

世界杯外围投注官网