蓝桥杯——生物芯片

心已赠人 2022-07-24 11:27 171阅读 0赞

> X博士正在研究一种生物芯片，其逻辑密集度、容量都远远高于普通的半导体芯片。博士在芯片中设计了 n 个微型光源，每个光源操作一次就会改变其状态，即：点亮转为关闭，或关闭转为点亮。这些光源的编号从 1 到 n，开始的时候所有光源都是关闭的。 博士计划在芯片上执行如下动作：  
> 所有编号为2的倍数的光源操作一次，也就是把 2 4 6 8 … 等序号光源打开  
> 所有编号为3的倍数的光源操作一次, 也就是对 3 6 9 … 等序号光源操作，注意此时6号光源又关闭了。  
> 所有编号为4的倍数的光源操作一次。  
> …..  
> 直到编号为 n 的倍数的光源操作一次。  
> X博士想知道：经过这些操作后，某个区间中的哪些光源是点亮的。  
> 【输入格式】  
> 3个用空格分开的整数：N L R （L < R < N < 10^15） 。N表示光源数，L表示区间的左边界，R表示区间的右边界。  
> 【输出格式】  
> 输出1个整数，表示经过所有操作后，\[L,R\] 区间中有多少个光源是点亮的。  
> 例如：  
> 输入：  
> 5 2 3  
> 程序应该输出：  
> 2  
> 再例如：  
> 输入：  
> 10 3 6  
> 程序应该输出：  
> 3  
> 资源约定：  
> 峰值内存消耗 < 256M  
> CPU消耗 < 1000ms

当时，拿到这道题的时候，下意识的就想去模拟，但是看到数据范围10^15，开数组开不到这麽大，如果去循环的话，有很容易超时，然后对这道题稍加分析，就可以获取到结果。

> 由题意得，所有光源的初始状态是关闭的，若要想使其最终是打开的状态，那么必须要经过奇数次这样的操作，而操作的次数其实就是光源的约数个数。因为没有”1的倍数进行的操作“，所以约数要减去1，即如果编号为n的光源，其有偶数个约数，那么最终这个光源是打开的。  
> 已知完全平方数有奇数个约数，非完全平方数有偶数个约数。（因为如果一个数x不是完全平方数，那么其约数一定是成对出现的，即一定有偶数个约数；而完全平方数，除去哪偶数个约数外，还有一个完全平方根，那么“偶+1=奇“）  
> 那么问题的答案就是给定区间\[L,R\]的非完全平方数的个数，区间\[L,R\]内的完全平方数的个数用A表示，非完全平方数的个数用B表示，则有B =（R-L+1) - A 。  
> 对于给定的数M，\[1,M\]内的其完全平方数有(int)sqrt(M)。则A=(int)sqrt(R)-(int)sqrt(L-1)  
> 最终问题的答案就是（R-L+1)-((long)sqrt(R)-(long)sqrt(L-1))

import java.util.Scanner;
    public class Main {
        public static long N,L,R;
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            N = in.nextLong();
            L = in.nextLong();
            R = in.nextLong();
            long sum = R - L + 1;//[L,R]区间共有多少个数
            long a = (long)(Math.sqrt(L-1));
            long b = (long)(Math.sqrt(R));
            System.out.println(sum-(b-a));
        }
    
    }