牛客 数码(枚举优化+数论思维)
程序员文章站
2023-10-15 21:03:33
传送门题面给定两个整数lll和rrr,对于所有满足1≤l≤x≤r≤1091 ≤ l ≤ x ≤ r ≤ 10^91≤l≤x≤r≤109 的xxx ,把xxx的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求1−91-91−9每个数码出现的次数。分析首先数据范围很大,问题可以转化为求1−(l−1)1-(l-1)1−(l−1)和1−r1-r1−r的因数。肯定不能暴力求每个数的因数。首先1−n1-n1−n的因数最多有2n2\sqrt{n}2n个,且会沿n\sqrt{n}n两边对称分...
题面
给定两个整数和,对于所有满足 的 ,把的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求每个数码出现的次数。
分析
首先数据范围很大,问题可以转化为求和的数码之差。肯定不能暴力求每个数的因数。首先的因数最多有个,且会沿两边对称分步且成对出现。设,考虑枚举范围内的因数,不难计算出的取值范围,举几个例子后不难发现只需要考虑几位数以及最高位是几,那么就枚举最高位和不超过的位数,当然得出的区间应该是的子区间,需要判断一下上下界的越界,之所以从开始是为了防止算重复
最后用了几个就是
讲解参考了牛客精讲
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=998244353;
const int maxn=2e5+10;
ll n,k;
ll num[20];
int solve(int x){
while(x>=10) x/=10;
return x;
}
void cal(int n,int s){
for(int i=1;i*i<=n;i++){
int y=n/i;
for(int j=1;j<=n;j*=10)
for(int k=1;k<=9;k++){
int d=max(j*k,i+1);
int u=min((k+1)*j-1,y);
if(d<=u) num[k]+=(u-d+1)*s;
}
num[solve(i)]+=(y-i+1)*s;
}
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int l,r;
cin>>l>>r;
cal(r,1);
cal(l-1,-1);
for(int i=1;i<=9;i++) cout<<num[i]<<endl;
return 0;
}
本文地址:https://blog.csdn.net/qq_44691917/article/details/107393608