您现在的位置是:首页 > 正文

数论题 (牛客网)

2024-01-30 20:05:46阅读 0
[编程|1000分] 数码
时间限制:1秒
空间限制:32768K
题目描述
给定两个整数 l 和 r ,对于所有满足1 ≤ l ≤ x ≤ r ≤ 10^9 的 x ,把 x 的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求1~9每个数码出现的次数。
输入描述:
一行,两个整数 l 和 r (1 ≤ l ≤ r ≤ 10^9)。


输出描述:
输出9行。

第 i 行,输出数码 i 出现的次数。

输入例子:
1 4

输出例子:
4
2
1
1
0
0
0
0
0
题解: 这题你正面去求每个数的约数绝对超时,反过来想如果 a*b 属于[l, r]里的话a和b就是符合条件的两个约数;所以就从1开始枚举a,对于每个a都可以确定一个b的范围(大概是[l/a, r/a], 具体情况代码里讲), 这里还要注意一下不能重复枚举,就要保证a <= b。 然后就可以统计了,对于a来说它做了(r/a-l/a+1)次,所以 res[a的最高位] += (r/a-l/a+1);对于b来说, l/a到r/a里的每个数都出现了一次,你普通的去遍历每个数再求出最高位也会超时, 具体看我代码怎么写的(这段代码好恶心);
上代码:
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int MAXN = 308;
const int MOD = 1e9;
int ff[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
LL res[10];

void addlr(int ll, int rr) {// 求上面所说的b;别看这代码短,很恶心,自己看吧;对了rr = 10^9时ff会越界,懒得改,反正能a;
    int tmp, i = 1, fir;
    while (ll <= rr) {
        tmp = ll%ff[i];
        if (!tmp) {i++; continue;}
        int k = (ff[i]-tmp)/ff[i-1];
        while (k-- && ll <= rr) {
            fir = ll;
            while (fir > 9)
                fir /= 10;
            res[fir] += ff[i-1];
            ll += ff[i-1];
        }
        i++;
    }
    res[fir] -= (ll-1-rr);
}

int main() {
    freopen("in.txt", "r", stdin);
    int l, r;
    scanf("%d%d", &l, &r);
    int mer = 1;
    while (1) {
        int ll = l/mer;//下面求左边界
        if (ll < mer) ll = mer;
        if (ll*mer < l) ll++;
        int rr = r/mer;//右边界
        if (ll > rr) break;//退出条件
        int tmp = mer;
        while (tmp > 9) tmp /= 10;//求mer的最高位
        res[tmp] += (rr-ll+1);//求上面题解所说的a的情况
        if (mer == ll) res[tmp]--;//这里要注意,如果 a*a 属于这个区间,a只能算一次,上面多算了,所以要减一个;
        addlr(ll, rr);
        mer++;
    }
    for(int i = 1; i < 10; i++)
        printf("%I64d\n", res[i]);
    return 0;
}



网站文章

  • 正则表达式的与或非

    正则表达式的与或非

    转自: http://www.cnblogs.com/bvbook/archive/2010/11/03/1867775.html正则表达式的与或非我们都知道,写正则表达式有点像搭积木,复杂的功能总可以拆分开来,由不同的元素(也就是子表达式)对应,再用合适的关系将它们组合起来,就可以完成。在这一节,我们讲解常见的与或非关系的表达。与“与”是最简单的关

    2024-01-30 20:05:38
  • 网络安全——缓冲区溢出攻击

    网络安全——缓冲区溢出攻击

    什么是缓冲区?它是指程序运行期间,在内存中分配的一个连续的区域,用于保存包括字符数组在内的各种数据类型。所谓溢出,其实就是所填充的数据超出了原有的缓冲区边界,并非法占据了另一段内存区域。两者结合进来,所谓缓冲区溢出,就是由于填充数据越界而导致原有流程的改变,黑客借此精心构造填充数据,让程序转而执行特殊的代码,最终获取控制权。

    2024-01-30 20:05:33
  • 2022年腾讯首发Java岗分布式面试真题,助力金三银四我是认真的!

    2022年腾讯首发Java岗分布式面试真题,助力金三银四我是认真的!

    分布式分为分布式缓存(Redis)、分布式锁(Redis 或 Zookeeper)、分布式服务(Dubbo 或 SpringCloud)、分布式服务协调(Zookeeper)、分布式消息队列(Kafk...

    2024-01-30 20:05:04
  • 山西大学计算机专业国内排名,山西这所大学曾是国内排名前五,如今排名下滑,有点走下坡路了...

    山西大学计算机专业国内排名,山西这所大学曾是国内排名前五,如今排名下滑,有点走下坡路了...

    文/山西有不少大家熟知的大学,一共85所院校,其中34所本科院校,51所专科院校。我国的高校数量众多,达到了2900多所,快突破了3000所,不仅数量多,各大高校也都经过的多年的办学历程,才达到现在办...

    2024-01-30 20:04:57
  • html必要的结构标准,HTML_关于现代前端必要知识

    html必要的结构标准,HTML_关于现代前端必要知识

    由VS Code空.html文件打出html:5或!按下tab建后默认生成的.html基本框架代码说起我是title第一行: 很庆幸,如今我们只需要这么一个自闭合标签即可告诉浏览器,请使用html5的...

    2024-01-30 20:04:51
  • centos7 安装git_centos7搭建H1ve环境

    centos7 安装git_centos7搭建H1ve环境

    H1ve是一款开源的ctf平台,具备解题和攻防对抗模式,并且还有可视化战况界面.是个很不错的平台,我们今天来搭建一下,顺便解决一下搭建的各种问题.系统版本:centos7需要环境:dockerpython2 pipdocker-composemariadb开始搭建,先重新安装一个centos7的虚拟机.(mini最小化安装,安装过程不表).1.先安装docker依赖环境yum insta...

    2024-01-30 20:04:23
  • CSS中修改ul标签的样式

    在我们使用li标签的时候,ul样式经常会错乱 ul标签样式设置如下: ul { list-style: none; padding: 0px; margin: 0px; }

    2024-01-30 20:04:17
  • aop执行模版

    aop执行模版

    【代码】aop执行模版。

    2024-01-30 20:04:09
  • 用计算机怎么算sin30,计算器sin30怎么按

    大家好,我是智能客服时间君,上述问题将由我为大家进行解答。以OPPO手机为例,在计算器上按sin30的方法如下:1、打开计算器。2、将手机横屏,并点击右下角的小图标,使手机屏幕变成横向。3、点击sin...

    2024-01-30 20:03:40
  • JVM参数-Xms和-Xmx的作用是什么

    JVM参数-Xms和-Xmx的作用是什么

    2024-01-30 20:03:33