怪数

[编程题]怪数

热度指数：1574 时间限制：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

输出

算法知识视频讲解

WMYW

//参考@初心者托奇的思路写的
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    unsigned int a,b;
    cin>>a>>b;
    int num=0;
    int i=0;
    while(pow(i,2)<a)
    {
        i++;
    }
    while(pow(i,2)<=b)
    {
        if((i-1)%2==0)
        {
            num+=pow(i,2)-a;
            a=pow(i,2);
            i++;
        }
        else
        {
            a=pow(i,2);
            i++;
        }
    }
    if((i-1)%2==0)
        num+=b-a+1;
    cout<<num;
    return 0;
}

编辑于 2020-04-23 12:01:59 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll F(ll x){
    if(x<0)
        return 0;
    else if(x==0)
        return 1;
    ll s=0, v = sqrt(x);
    if(v%2){
        s = v*(v+1)/2;
    }else{
        ll t = v-1;
        s = t*(t+1)/2;
        s += x-v*v+1;
    }
    return s;
}

int main(){
    ll a, b;
    cin>>a>>b;
    cout<<F(b)-F(a-1)<<endl;

    return 0;
}

发表于 2019-11-21 23:38:42 回复(0)

初心者托奇

找规律呗，它要你输出数量，又不是真要你去算哪些符合要求~

观察可得，[i^2,(i + 1)^2)中的数为怪数（i为一切偶自然数，左闭右开区间）。

例如，0是怪数，123不是怪数，45678是怪数，9101112131415又不是怪数，16~24又是怪数，25~35又不是怪数……

找到规律就so easy了。

a,b = list(map(int,input().split())),[0,0]
for i in range(2):
    b[i] = sum([j * 2 - 1 for j in range(1,int(a[i] ** 0.5) + 1,2)])
    if 1 - int(a[i] ** 0.5) % 2:
        b[i] += a[i] - int(a[i] ** 0.5) ** 2 + i
print(b[1] - b[0])

编辑于 2020-03-17 15:58:07 回复(0)

Java

雷欧尼桑

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

༒copy怪

//不能没有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)

Python 3

波千鸟

a, b = list(map(int, input().split(" ")))
s = 0

i = int(a ** 0.5)
if i % 2 == 0:
    if (i + 1) ** 2 >= a:
        s += (i + 1) ** 2 - a
    i += 2
else:
    i += 1
while i ** 2 <= b:
    if (i + 1) ** 2 <= b:
        s += (i + 1) ** 2 - i ** 2
    else:
        s += b - i ** 2 + 1
    i += 2
print(s)

发表于 2021-08-18 16:34:40 回复(0)

jackchengxing

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为20.00%

#include<bits/stdc++.h>

using namespace std;
int cnt=0;
void func(int i){
if((i&1)==0){
if(i==0) cnt++;
else if(i==2) return;
else{
int shang=0;
for(int j=3;2*j<=i;j++)
shang+=i/j;
if((shang&1)==0) cnt++;
}

}
else{
if(i<=3) return;
int shang=(i+1)/2+i;
for(int j=2;2*j<i;j++)
shang+=i/j;
if((shang&1)==0) cnt++;
}

}
int main(){
int a,b;
cin>>a>>b;
for(int i=a;i<=b;i++){
func(i);
}
cout<<cnt;
return 0;
}

发表于 2019-05-19 21:57:08 回复(2)