CF117B 题解

Peter0701

2019-09-17 15:59:31

Solution

给定两非负整数 $a,b$ 以及模数 $mod$ ,求两个由 $9$ 位数字构成的字符串 $A,B$ (允许包含前导 $0$ )相连后对 $mod$ 取模的值能否为 $0$ ,要求 $A$ 的值不超过 $a$ , $B$ 的值不超过 $b$ 。若取模后的值不能为 $0$ 的话,还要输出字典序最小的使取模后的值不为 $0$ 的字符串 $A$ 。 看起来很有博弈论的味道。实际上可以通过一些数学方法转化为可做的题目: 因为取模会使得循环节出现,所以如果 $a>mod$ ,我们可以只考虑一个循环节内 $A$ 的取值;否则 $A$ 就只要考虑取 $[0,a]$ 之间的整数。这是本题合理复杂度的保证。 那么我们只需要预处理出 $B$ 能够得到的值,然后枚举 $A$ ,判断是否能出现一个 $A$ 不能和任何一个 $B$ 组合能被 $mod$ 整除的情况。如果出现的话,这个 $A$ 就是字典序最小的字符串 $A$ ;如果一整个循环节中都没有出现可行解,那么取模后的值就不能为 $0$ 了。 有疑问的评论区见! 代码如下: ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int a,b,mod,ans; inline int solve(int a,int b,int mod) { int p=1000000000%mod; if(!p) return -1; if(b>=mod-1) return -1; int j=0; for(register int i=0;i<=min(a,mod);i++) { if(j>b) return i; j-=p; if(j<0) j+=mod; } return -1; } int main() { a=read(); b=read(); mod=read(); ans=solve(a,b,mod); if(ans==-1) printf("2\n"); else printf("1 %09d\n",ans); return 0; } ```