首页 > 试题广场 >

怪数

[编程题]怪数
  • 热度指数:1556 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

M突然对怪数产生了兴趣。假设一个数n,如果[n/1]+[n/2]+...+[n/k](k为趋近于正无穷的正整数)为一个偶数,那么这个数是一个怪数,现在给定一个区间[a,b],求[a,b]之间有多少怪数。

[x]表示不大于x的最大整数。


输入描述:
输入只包含一行,有两个非负整数a,b(0<=a,b<=2^31,a<=b)。


输出描述:
输出区间[a,b]中的怪数的个数。
示例1

输入

0 10

输出

6
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = reader.readLine().split(" ");
        long a = Long.parseLong(s[0]);
        long b = Long.parseLong(s[1]);
        // 结果为0~b怪数个数 - 0~a-1怪数个数
        System.out.println(handle(b) - handle(a - 1));
    }

    // 计算0~num共有几个怪数
    // 规律:怪数与非怪数相间,且成公差为2等差数列
    // 即1个怪数、3个非怪数、5个怪数、7个非怪数、9个怪数...,以此类推和为平方数
    public static int handle(long num) {
        int res = 0;
        int sq = (int) Math.sqrt(num);
        int k = (sq + 1) / 2;
        res += k * (2 * k - 1);
        if ((sq & 1) == 0) {
            res += num - sq * sq + 1;
        }
        return res;
    }
}







发表于 2024-03-23 22:09:22 回复(0)
//不能没有Java的一席之地!!!!
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
//         int a = sc.nextInt();
//         int b = sc.nextInt();
        String a1 = sc.next();
        String b1 = sc.next();
        Long a = Long.parseLong(a1);
        Long b = Long.parseLong(b1);
        int num=0;
        int start = 0;
        while(Math.pow(start, 2)<a)
            start++; //找到a是第几个数的平方
        while(Math.pow(start,2)<=b){
            if(start%2==0){
                a=(long)Math.pow(start,2);//a就是start的平方这个怪数
                start++;//接着找其他的
            }else{
                num+=Math.pow(start, 2)-a;
                a=(long)Math.pow(start, 2);//记住a的位置,为了找不完整的怪数
                start++;//接着往下找
            }
        }
        //找完完整的后,加上不完整的,也就是最后一段
        if(start%2!=0)
            num+=b-a+1;
        System.out.print(num);
        
        
        
    }
}
点点赞,收藏一下,新人水经验勋章哈哈
发表于 2022-03-23 17:10:22 回复(1)