题解：AT_arc050_c [ARC050C] LCM 111

一道比较简单的题。~~（我绝对不会告诉你这题我改了很久）~~

题目意思很简单，我就不过多解释了，我们直接进入正题。

题目要我们求 $a$ 个 $1$ 组成的数与 $b$ 个 $1$ 组成的数的最小公倍数除以 $m$ 后的余数。先不考虑多的，我们先设定一个函数 $\operatorname{change}(x)$ 表示由 $x$ 个 $1$ 组成的数，也就是这个：

$\operatorname{change}(x)=\underbrace{111111...11}_{x\text{个}1}$

写的更加数学化一点就是：

$\operatorname{change}(x)=\frac{10^x-1}{9}$

那么我们要求的答案就是：

$\operatorname{lcm}(\operatorname{change}(a),\operatorname{change}(b))\bmod m$

同时又有 $\operatorname{lcm}(x,y)=x\times y\div\operatorname{gcd}(x,y)$ 。

所以说：

$ans=\operatorname{change}(a)\times\operatorname{change}(b)\div\operatorname{gcd}(\operatorname{change(a)},\operatorname{change(b)})\bmod m$

但我们仔细发现： $\operatorname{gcd}(\operatorname{change}(a),\operatorname{change}(b))$ 这东西也不好求啊，如果我们能把它转化成 $a$ 和 $b$ 之间的关系就好了。

那么接下来，让我们用感性的思维去看一看这个式子，直觉告诉我们： $\operatorname{gcd}(\operatorname{change}(a),\operatorname{change}(b))=\operatorname{change}(\operatorname{gcd}(a,b))$ 。以下是证明过程。

证明： 假设 $\underbrace{1111...11}_{t\text{个}1}$ 同时是 $\underbrace{11111...11}_{a\text{个}1}$ 与 $\underbrace{111111...11}_{b\text{个}1}$ 的公因数，则：

$\underbrace{111111...11}_{b\text{个}1}=\underbrace{1111...11}_{t\text{个}1}\times1\underbrace{000...00}_{t-1\text{个}0}1\underbrace{000...00}_{t-1\text{个}0}1...1\underbrace{000...00}_{t-1\text{个}0}1\\\underbrace{11111...11}_{a\text{个}1}=\underbrace{1111...11}_{t\text{个}1}\times1\underbrace{000...00}_{t-1\text{个}0}1\underbrace{000...00}_{t-1\text{个}0}1...1\underbrace{000...00}_{t-1\text{个}0}1$

第一个式子中 $\underbrace{000...00}_{t-1\text{个}0}1$ 这样的循环一共有 $\frac{b}{t}$ 个，第二个式子中这样的循环则有 $\frac{a}{t}$ 个，因为要有整数个循环，所以 $\frac{b}{t}$ 和 $\frac{a}{t}$ 都是整数，所以 $t$ 是 $a, b$ 的公因数。而我们要 $\underbrace{1111...11}_{t\text{个}1}$ 最大，所以 $t$ 就要是 $a, b$ 的最大公因数，即 $t=\operatorname{gcd}(a,b)$ 。

由上，我们可以得到：

$\operatorname{gcd}(\underbrace{11111...11}_{a\text{个}1},\underbrace{111111...11}_{b\text{个}1})=\underbrace{111111...11}_{t\text{个}1}=\underbrace{111111...11}_{\operatorname{gcd}(a,b)\text{个}1}$

转化一下就成了：

$\operatorname{gcd}(\operatorname{change}(a),\operatorname{change}(b))=\operatorname{change}(\operatorname{gcd}(a,b))$

所以，我们得到了这样一个等式：

$ans=\operatorname{change}(a)\times\operatorname{change}(b)\div\operatorname{change}(\operatorname{gcd}(a,b))$

但这样我们又要算三遍 $\operatorname{change}(x)$ ，有没有什么办法可以优化？

这里呢我是采用了倍分的思想。

在上面的证明过程中，我们将 $\underbrace{111111...11}_{b\text{个}1}$ 拆成了 $\underbrace{1111...11}_{t\text{个}1}\times1\underbrace{000...00}_{t-1\text{个}0}1\underbrace{000...00}_{t-1\text{个}0}1...1\underbrace{000...00}_{t-1\text{个}0}1$ ，我们沿用这个思路，如果我们把 $\operatorname{change}(a)$ 归为一类， $\operatorname{change}(b)\div\operatorname{change}(\operatorname{gcd}(a,b))$ 归为一类，那我们就只需要解决后半部分值的问题就行了，后半部分又该怎么做呢？

我们将这个式子转化一下，就成了:

$\begin{equation}\begin{split}&\operatorname{change}(b)\div\operatorname{change}(t)\\&=\underbrace{111111...11}_{b\text{个}1}\div\underbrace{1111...11}_{t\text{个}1}\\&=1\underbrace{000...00}_{t-1\text{个}0}1\underbrace{000...00}_{t-1\text{个}0}1...1\underbrace{000...00}_{t-1\text{个}0}1\end{split}\end{equation}$

而这又有 $\frac{b}{t}$ 个循环，因为 $t=\operatorname{gcd}(a,b)$ ，所以就有 $b\div\operatorname{gcd}(a,b)$ 个循环。到这，整个思路就彻底结束了。

代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,m;
int gcd(int x,int y) {if(y==0) {return x;}return gcd(y,x%y);
}
int qpow(int x,int y) {//快速幂int z=1;while(y) {if(y&1) {z=z*x%m;}y>>=1;x=x*x%m;}return z;
}
int answer(int x,int y) {int now=1,po=qpow(10,y),ans=0;while(x) {if(x&1) {ans=(ans*po%m+now)%m;}x>>=1;now=(now*po%m+now)%m;po=po*po%m;}return ans;
}
signed main() {cin>>a>>b>>m;int g=gcd(a,b);cout<<answer(a,1)*answer(b/g,g)%m;//一共有b/g个循环，每次要乘10^greturn 0;
}

题解：AT_arc050_c [ARC050C] LCM 111

相关资讯

热文排行

最新新闻

推荐新闻

热搜词