2024CCPC郑州邀请赛暨河南省赛（A,B,C,D,F,G,H,J,K,L,M）

2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest

2024 年中国大学生程序设计竞赛全国邀请赛（郑州）暨第六届 CCPC 河南省大学生程序设计竞赛

比赛链接

这场的题说实话难度其实都不大（除了 E E E 和 I I I），但是做法很固定，考思维，想到了一拍脑袋就出，想不到就寄，因此很多强队都翻车了。这场 13 13 13 题其中的 11 11 11 题我觉得都可以赛时出。

是时候祭出这张图了：

Problem A. Once In My Life

题意：

对于小 A A A 而言，数位包含 1 ∼ 9 1 ∼ 9 1∼9，并且至少两个数位是 d （ 1 ≤ d ≤ 9 ） d（1 ≤ d ≤ 9） d（1≤d≤9）的十进制正整数都是幸运数。

当 d = 3 d = 3 d=3 时，显然 1234567890123 1234567890123 1234567890123 是小 A A A 的幸运数，但 987654321 987654321 987654321 因为数位 3 3 3 仅出现了一次而不是幸运数， 998244353 998244353 998244353 因为缺少数位 1 , 6 , 7 1, 6, 7 1,6,7 而不是幸运数。

现在小 A A A 有一个正整数 n n n，并给出正整数 d d d。他想找到正整数 k k k 使得二者的乘积 n ⋅ k n · k n⋅k 是幸运数。

你能用计算机辅助他的计算吗？

输出保证 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k≤2∗1010

思路：

本质是个构造题，需要一点点数论知识。

我们想要 n k nk nk 得到的数里有 123456789 123456789 123456789 和额外的一个 d d d，那么我们就构造出来，假设结果是 123456789 d 123456789d 123456789d，构造得到的数不一定是 n n n 的倍数，但是我们可以加一些数让它成为倍数，不过这就破坏了这十个位置上的数字。

考虑到当 k k k 乘以 10 10 10 的时候， 123456789 d 123456789d 123456789d 也会乘以 10 10 10，相当于整体向左移动一位，低位就空出来了，这时我们给低位增加一些数字的时候，就不会影响到高处的十个位置了。最简单的想法就是反正 n ≤ 1 0 8 n\le10^8 n≤108，所以我们只要低八位空出来就行了，这时就会得到 123456789 d 00000000   m o d   n = x 123456789d00000000\bmod n=x 123456789d00000000modn=x，我们再加上 ( n − x )   m o d   n (n-x)\bmod n (n−x)modn 就是乘积，除以 n n n 就是 k k k 了。

不过题目要求 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k≤2∗1010，当 n ≤ 1 0 7 n\le 10^7 n≤107 时，上面构造出来的数铁定 > 2 ∗ 1 0 10 \gt 2*10^{10} >2∗1010。考虑到我们没必要低位留 8 8 8 位，比如 n n n 只有一位数的时候，我们低位就只留一位就行了，如果 n n n 是 t t t 位数，那么我们低位就只留 t t t 位就可以了，这样构造出来的数 k k k 就是一个小于 2 ∗ 1 0 10 + t − 1 2*10^{10+t-1} 2∗1010+t−1 的数，除以一个大于 1 0 t − 1 10^{t-1} 10t−1 的数，得到的数肯定小于 2 ∗ 1 0 10 2*10^{10} 2∗1010。

code：

#include #include using namespace std;typedef long long ll;int T;ll n,d;ll pw[20];int main(){cin.tie(0)->sync_with_stdio(false);pw[0]=1;for(int i=1;i>T;while(T--){cin>>n>>d;int i=0;while(pw[i]cinn;for(int i=1,c;icinc;while(!sta.empty() && sta.back().first=c)sta.pop_back();sta.push_back({c,i});}int p=0,rm=0,ans=0;for(auto [c,i]:sta){rm+=i-p;p=i;ans+=rm/c;rm-=rm/c*c;}coutint n;cinn;vectorcina[i];pos.push_back({a[i],i});}sort(pos.begin(),pos.end());int p = 1;int ans = 0;int was = 0;for(PII pii : pos){if(pii.second