数码

admin管理员组

文章数量:1122852

数码

题目

给定两个整数l和r,对于任意x,满足l≤x≤r,把x所有约数写下来。
对于每个写下来的数，只保留最高位的那个数码。求[1,9]中每个数码出现的次数.
1≤l≤r≤10^9

解析：
如果正面去想每个数的约数，绝对超时，反过来如果a*b属于[l,r]，那么a,b是符合条件的约数，

首先考虑约数i会被统计r/i-（l-1）/i次，鉴于其形式相同，考虑怎么统计r/i

分块

1、当约数i<sqrt®时只有sqrt®种情况，可以暴力统计

2、当约数i>=sqrt®时，约数r/i只有sqrt®种情况，可以把出现次数相同的约数统一统计

出现i次的约数是r/(i+1)+1到r/i，是连续的，那这些数有多少以1开头哪？其实可以统计该区间与{[1,1],[10,19],[100,199],[1000,1999]…}的重合部分的数量，这样就可以算了。

总复杂度O（sqrt（n）*log（n））

#include <iostream>
#include <cstdio>
#include <cmath>typedef long long LL;
using namespace std;LL cnt[11];int f(int x) {while (x >= 10) x /= 10;return x; 
}//统计[l,r]区间中统计了v次，且第一位数字为tp的约数
void Add(LL l,LL r,int v,int tp) {LL opr = tp, opl = tp;while(opl <= r) {if(opr >= l) cnt[tp] += v*(min(r,opr)-max(l,opl)+1LL);opl = opl*10;opr = opr*10+9;} 
}void calc(int r,int cas) {int lim = (int)sqrt(r);	for (int i = 1; i <= lim; i++)//这个i代表的是统计相同次数的，for (int j = 1; j <= 9; j++)//这j表示约数开头为jAdd(r/(i+1)+1,r/i,cas*i,j);for (int i = r/(lim+1); i >= 1; i--) cnt[f(i)] += cas*r/i;  //统计不在分组之内其他
}int main() {int l,r; cin >> l >> r;calc(r,1); calc(l-1,-1);for (int i = 1; i <= 9; i++) printf("%lld\n",cnt[i]);return 0;
}

有纸质的

本文标签： 数码