P8982 下坠题解

masonpop · 2023-02-03 09:57:18 · 题解

非常好的一道题。感觉是一道数学题和一个魔幻贪心的拼接。

感谢出题组和负责人对蒟蒻的热情帮助。
回归正题。发现每一位 +1 的范围是 [2,10]。注意到，带 0 的位是没有作用的，因为不会改变数值，而且对最小值没有任何帮助。
由于是 2 到 10 内的数相乘得到，那么 f(y) 能取到的值必定形如 2^a3^b5^c7^d。反之容易验证也成立。
这是重要的一步。做题多的同学可以想到 P1748 正好说的就是这件事。那么，我们就可以维护四个指针 a,b,c,d，表示可能通过乘 2,3,5,7 得到当前数的位置。(听不懂的同学可以参考那道题第一篇题解或者手动模拟下我这个过程，也可以先 \color{green}\text{A} 了那道题再来看这道题）。
而且，注意到如果 y\leq 10^{18}，那么 f(y) 也一定不超过 10^{18} 的范围。这是因为显然当 y 取 10^{18}-1 即 18 个 9 时，f(y) 取最大值 10^{18}。但反之，不是所有的下坠数对应的最小 y 都满足范围。因此，我们可以先生成 [1,10^{18}] 的所有下坠数，实在不行就暴力生成再排序（指数不可能太大）。这部分的复杂度是 O(T),T 是范围内下坠数的个数。代码如下。
```
int a=0,b=0,c=0,d=0;
h[0]=1;
for(int i=1;i;i++)
{
    h[i]=min(min(h[a]*2,h[b]*3),min(h[c]*5,h[d]*7));
    if(h[i]>1e18)break;
    tot=i;
    if(h[i]==h[a]*2)a++;
    if(h[i]==h[b]*3)b++;
    if(h[i]==h[c]*5)c++;
    if(h[i]==h[d]*7)d++;
}
```
打完表发现这样的数出去 1 只有 66060 个。因此如果 k>66060 就可以直接报告无解了。
再考虑怎么根据 f(y) 的值求最小的 y。显然要将 y 拆成 [2,10] 的数相乘，再减一依次输出。这里有一步贪心，即如下结论。

结论：从大到小，能拆分就一定拆分。

我们可以简单证明一下，就以 10 为例吧。
比如你在一个数 x 中有 10 的时候不去拆 10，考虑到质因子 2,5 一定在 2,4,5,8 中，而无论是拆成 4,5 还是 5,8 显然没有 2,10 和 4,10 优。拆成 2,5 显然不可取，因为位数增加了。
其他数类似，从大到小依次证明即可。
那么按照上述过程拆分即可。
注意一个小细节，就是上面所说的，我们需要判断拆分成的这个最小的数是否在 [1,10^{18}] 内。直接判断其位数与 18 的大小关系即可，若 >18 就报告无解。
这部分的时间复杂度是 O(1)，最坏运算 20 次左右。
总时间复杂度是 O(T+Qc),c 是一个小常数。

代码可能没有出题人的简单，因为询问是直接一个一个除的，但是清晰易懂。

#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
int t,k;
int h[114514];
int tot;
signed main()
{
int a=0,b=0,c=0,d=0;
h[0]=1;
for(int i=1;i;i++)
{
    h[i]=min(min(h[a]*2,h[b]*3),min(h[c]*5,h[d]*7));
    if(h[i]>1e18)break;
    tot=i;
    if(h[i]==h[a]*2)a++;
    if(h[i]==h[b]*3)b++;
    if(h[i]==h[c]*5)c++;
    if(h[i]==h[d]*7)d++;
}
scanf("%llu",&t);
while(t--)
{
    int k;
    scanf("%llu",&k);
    if(k>tot)printf("-1 ");
    else
    {
        int tmp=h[k];
        int cnt2,cnt3,cnt4,cnt5,cnt6,cnt7,cnt8,cnt9,cnt10;
        cnt2=cnt3=cnt4=cnt5=cnt6=cnt7=cnt8=cnt9=cnt10=0;
        while(tmp && tmp%10==0)tmp/=10,cnt10++;
        while(tmp && tmp%9==0)tmp/=9,cnt9++;
        while(tmp && tmp%8==0)tmp/=8,cnt8++;
        while(tmp && tmp%7==0)tmp/=7,cnt7++;
        while(tmp && tmp%6==0)tmp/=6,cnt6++;
        while(tmp && tmp%5==0)tmp/=5,cnt5++;
        while(tmp && tmp%4==0)tmp/=4,cnt4++;
        while(tmp && tmp%3==0)tmp/=3,cnt3++;
        while(tmp && tmp%2==0)tmp/=2,cnt2++;
        if(cnt2+cnt3+cnt4+cnt5+cnt6+cnt7+cnt8+cnt9+cnt10>18)
        {
            printf("-1 ");
            continue;
        }
        for(int i=1;i<=cnt2;i++)printf("1");
        for(int i=1;i<=cnt3;i++)printf("2");
        for(int i=1;i<=cnt4;i++)printf("3");
        for(int i=1;i<=cnt5;i++)printf("4");
        for(int i=1;i<=cnt6;i++)printf("5");
        for(int i=1;i<=cnt7;i++)printf("6");
        for(int i=1;i<=cnt8;i++)printf("7");
        for(int i=1;i<=cnt9;i++)printf("8");
        for(int i=1;i<=cnt10;i++)printf("9");
        printf(" ");
    }
}
return 0;
}

总结：遇到这种带有数学性质的题目时，要好好分析题目里面的条件，大胆猜结论，先猜后证，避免朝一个方向上死磕。

希望这篇题解能帮到其他同学，写这篇题解同样加深了我对这道题的理解。

P8982 下坠 题解

P8982 下坠题解