欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

牛客 数码(枚举优化+数论思维)

程序员文章站 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​两边对称分...

传送门


题面

给定两个整数llrr,对于所有满足1lxr1091 ≤ l ≤ x ≤ r ≤ 10^9xx ,把xx的所有约数全部写下来。对于每个写下来的数,只保留最高位的那个数码。求191-9每个数码出现的次数。

分析

首先数据范围很大,问题可以转化为求1(l1)1-(l-1)1r1-r的数码之差。肯定不能暴力求每个数的因数。首先1n1-n的因数最多有2n2\sqrt{n}个,且会沿n\sqrt{n}两边对称分步且成对出现。设x=abx=a*b,考虑枚举1n1-\sqrt{n}范围内的因数aa,不难计算出bb的取值范围[1,ra][1,⌊\frac{r}{a}⌋],举几个例子后不难发现只需要考虑几位数以及最高位是几,那么就枚举最高位和不超过bb的位数,当然得出的区间应该是[a+1,b][a+1,b]的子区间,需要判断一下上下界的越界,之所以从a+1a+1开始是为了防止算aa重复

最后aa用了几个就是ba+1b-a+1

讲解参考了牛客精讲

#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

相关标签: 牛客比赛