当前位置： 移动技术网 > 移动技术>移动开发>Android > 牛客 数码（枚举优化+数论思维）

牛客 数码（枚举优化+数论思维）

2020年07月18日  | 移动技术网移动技术  | 我要评论

传送门

题面

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

分析

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

最后aa用了几个就是b−a+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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网