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

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

题目描述

$1 le T le 10^4,1le mle 100,0le a_ile 10^{18}$.

题目分析

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

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

题目给了$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} ight floor}=e$.

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

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 typedef unsigned long long ull;
 4 
 5 int T;
 6 bool vis[10035];
 7 ll m,pr[103],ans;
 8 
 9 ll read()
10 {
11     char ch = getchar();
12     ll num = 0, fl = 1;
13     for (; !isdigit(ch); ch=getchar())
14         if (ch=='-') fl = -1;
15     for (; isdigit(ch); ch=getchar())
16         num = (num<<1)+(num<<3)+ch-48;
17     return num*fl;
18 }
19 void makePrime()
20 {
21     for (int i=2; i<=1000; i++)
22     {
23         if (!vis[i]) pr[++pr[0]] = i;
24         if (pr[0]==100) break;
25         for (int j=2; j*i<=1000; j++)
26             vis[i*j] = true;
27     }
28 }
29 void write(ll x){if (x/10) write(x/10);putchar(x%10+'0');}
30 int main()
31 {
32     makePrime();
33     for (T=read(); T; --T)
34     {
35         m = read(), ans = 1;
36         for (int i=1; i<=m; i++)
37         {
38             ll e = read(), cnt = 0, base = 1, val = pr[i], p = pr[i];
39             while (base*p+1 <= e)
40                 base = base*p+1, val *= p;
41             for (; base; base/=p,val/=p)
42                 cnt += val*(e/base), e -= base*(e/base);
43             ans = std::max(ans, cnt);
44         }
45         write(ans), putchar('
');
46     }
47     return 0;
48 }

END