【数位贪心】loj#530. 「LibreOJ β Round #5」最小倍数

记录一下题解里写的算法四

题目描述

$1 \le T \le 10^4,1\le m\le 100,0\le a_i\le 10^{18}$.

题目分析

题解里的算法四是这么写的

主要是这个$\alpha_i = \sum_{k = 1}^{\infty}{\left \lfloor \frac{N}{\mathrm{pr}_i^k} \right \rfloor}$的计算在蛮多地方有看到应用，所以这里记一下对算法四的理解。

题目给了$m$个$e_i$的限制，要求满足$\alpha_i \ge e_i$.首先由于这$m$个限制之间互相并不影响，所以答案$N=\max\{N_i\}$，其中$N_i$表示最小的满足第$i$个限制的数。这样只需要来考虑如下问题：

给定$\alpha,e,质数p$，求最小的$N$满足$\sum_{k = 1}^{\infty}{\left \lfloor \frac{N}{\mathrm{p}^k} \right \rfloor}=e$.

比较常见的套路是把$N$按$p$进制拆分成$(x_1 x_2 \cdots x_m)_{p}$。接下去考虑一个从右往左第$k+1$位$v \cdot \mathrm{p}^k$对$e$的贡献，由于它会在$k=1\cdots \mathrm{p}^k$时被计入，所以是$(v v \cdots v)_{\mathrm{p}}$（k个v）.注意到这相当于是一个类似进制拆分的过程，那么就可以从高位到低位贪心地计算$N_i$。

 #include<bits/stdc++.h>

 typedef long long ll;

 typedef unsigned long long ull;

 int T;

 bool vis[];

 ll m,pr[],ans;

 ll read()

 {

     char ch = getchar();

     ll num = , fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = -;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     return num*fl;

 }

 void makePrime()

 {

     for (int i=; i<=; i++)

     {

         if (!vis[i]) pr[++pr[]] = i;

         if (pr[]==) break;

         for (int j=; j*i<=; j++)

             vis[i*j] = true;

     }

 }

 void write(ll x){if (x/) write(x/);putchar(x%+'');}

 int main()

 {

     makePrime();

     for (T=read(); T; --T)

     {

         m = read(), ans = ;

         for (int i=; i<=m; i++)

         {

             ll e = read(), cnt = , base = , val = pr[i], p = pr[i];

             while (base*p+ <= e)

                 base = base*p+, val *= p;

             for (; base; base/=p,val/=p)

                 cnt += val*(e/base), e -= base*(e/base);

             ans = std::max(ans, cnt);

         }

         write(ans), putchar('\n');

     }

     return ;

 }

END

巴特西

【数位贪心】loj#530. 「LibreOJ β Round #5」最小倍数

题目描述

题目分析

最新文章

热门文章