本文主要是介绍[ARC050C] LCM 111 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一句话题解:
转化两个大数的 gcd \gcd gcd ,再用迭代的思想求答案。
[ARC050C] LCM 111 题解
题目
题意
给你 a a a , b b b , m m m ,其中 1 ≤ A , B ≤ 1 0 18 , 2 ≤ M ≤ 1 0 9 1\le A,B\le 10^{18},2\le M\le 10^9 1≤A,B≤1018,2≤M≤109 ,让你求 a a a 个 1 1 1 和 b b b 个 1 1 1 的最小公倍数。
思路
我们构造一个函数 o n e ( x ) \mathrm{one}(x) one(x) 表示 x x x 个 1 1 1 拼接起来,用数学语言表述就是:
o n e ( x ) = 1 0 x 9 \mathrm{one}(x) = \frac{10 ^ x}{9} one(x)=910x
同时又有 l c m ( a , b ) = a ∗ b / gcd ( a , b ) \mathrm{lcm}(a, b) = a * b / \gcd(a, b) lcm(a,b)=a∗b/gcd(a,b) ,那么我们要求的就转化成了
o n e ( a ) ∗ o n e ( b ) / gcd ( o n e ( a ) , o n e ( b ) ) \mathrm{one}(a) * \mathrm{one}(b) / \gcd(\mathrm{one}(a), \mathrm{one}(b)) one(a)∗one(b)/gcd(one(a),one(b))
因为 o n e ( a ) \mathrm{one}(a) one(a) 与 o n e ( b ) \mathrm{one}(b) one(b) 都比较好求,所以此时的问题就转移到了怎么求 gcd ( o n e ( a ) , o n e ( a ) ) \gcd(\mathrm{one}(a), \mathrm{one}(a)) gcd(one(a),one(a)) 上来。
我们先尝试感性理解一下。可以发现:
gcd ( o n e ( a ) , o n e ( a ) ) = o n e ( gcd ( a , b ) ) \gcd(\mathrm{one}(a), \mathrm{one}(a)) = \mathrm{one}(\gcd(a, b)) gcd(one(a),one(a))=one(gcd(a,b))
如何证明?我们可以这样想(本人数学不好,如有错误,还请大佬谅解orz):
方法一
假设 d ∣ a d \mid a d∣a ,那么存在 o n e ( d ) ∣ o n e ( a ) \mathrm{one}(d) \mid \mathrm{one}(a) one(d)∣one(a) ,因为我们可以把 o n e ( a ) \mathrm{one}(a) one(a) 恰好分成 d d d 个 1 1 1 一组, o n e ( a ) \mathrm{one}(a) one(a) 除以 o n e ( d ) \mathrm{one}(d) one(d) 之后,每组还剩一个一,并且商是一个整数。
因为 gcd ( a , b ) ∣ a \gcd(a, b) \mid a gcd(a,b)∣a 且 gcd ( a , b ) ∣ b \gcd(a, b) \mid b gcd(a,b)∣b ,
所以 o n e ( gcd ( a , b ) ) ∣ o n e ( a ) \mathrm{one}(\gcd(a, b)) \mid \mathrm{one}(a) one(gcd(a,b))∣one(a) 且 o n e ( gcd ( a , b ) ) ∣ o n e ( b ) \mathrm{one}(\gcd(a, b)) \mid \mathrm{one}(b) one(gcd(a,b))∣one(b) ,并且不可能存在比 o n e ( gcd ( a , b ) ) \mathrm{one}(\gcd(a, b)) one(gcd(a,b)) 更大的满足条件的数。
方法二(比较抽象、不严谨)
显而易见,存在:
o n e ( a ) m o d o n e ( b ) = o n e ( a m o d b ) \mathrm{one}(a) \bmod \mathrm{one}(b) = \mathrm{one}(a \bmod b) one(a)modone(b)=one(amodb)
那么就有:
gcd ( o n e ( a ) , o n e ( b ) ) = gcd ( o n e ( b ) , o n e ( a ) m o d o n e ( b ) ) = gcd ( o n e ( b ) , o n e ( a m o d b ) ) \gcd(\mathrm{one}(a), \mathrm{one}(b)) = \gcd(\mathrm{one}(b), \mathrm{one}(a) \bmod \mathrm{one}(b)) =\gcd(\mathrm{one}(b), \mathrm{one}(a \bmod b)) gcd(one(a),one(b))=gcd(one(b),one(a)modone(b))=gcd(one(b),one(amodb))
当 b = = 0 b == 0 b==0 时, o n e ( b ) = = 0 \mathrm{one}(b) == 0 one(b)==0。
所以在求
gcd
的过程中其实就是把 a a a 和 b b b 套在了 o n e ( ) \mathrm{one}() one() 里面,最后算出来就是 o n e ( gcd ( a , b ) ) \mathrm{one}(\gcd(a, b)) one(gcd(a,b)) 。
此时答案就变成了:
o n e ( a ) ∗ o n e ( b ) / o n e ( gcd ( a , b ) ) \mathrm{one}(a) * \mathrm{one}(b) / \mathrm{one}(\gcd(a, b)) one(a)∗one(b)/one(gcd(a,b))
我们把这个式子分成两组:
o n e ( a ) \mathrm{one}(a) one(a)
o n e ( b ) / o n e ( gcd ( a , b ) ) \mathrm{one}(b) / \mathrm{one}(\gcd(a, b)) one(b)/one(gcd(a,b))
接下来我们讨论对于这两组式子的求解方式。下文将省略模运算!!!
Tips:语言描述比较抽象,如果看不懂可以先尝试看看代码。
第一组
我们先从简单的说起。定义 f i f_i fi 表示 o n e ( i ) \mathrm{one}(i) one(i) ,写成递推式就是:
f i = ( 10 ∗ f i − 1 + 1 ) f_i = (10 * f_{i - 1} + 1) fi=(10∗fi−1+1)
但是这样实现的话时间复杂度达到了 O ( n ) O(n) O(n) ,过不了一点。我们根据数据范围进行推测:要么是 O ( 1 ) O(1) O(1) ,要么是 O ( log n ) O(\log n) O(logn) 。 O ( 1 ) O(1) O(1) 不大可能,考虑 O ( log n ) O(\log n) O(logn) 做法。
我们发现,可以用迭代的思想。我们把 a a a 写作一个二进制数。比如:
5 = ( 101 ) 2 = 2 2 + 2 0 = 4 + 1 5 = (101)_2 = 2 ^ 2 + 2 ^ 0 = 4 + 1 5=(101)2=22+20=4+1
那么我们就可以把 4 4 4 个 1 1 1 和 1 1 1 个 1 1 1 拼在一起。
考虑维护一个 n o w now now 值与一个 p o w pow pow 值。最初 n o w = 1 , p o w = 10 now = 1, pow = 10 now=1,pow=10 。假设现在算了 x x x 位,那么 n o w = o n e ( a ) , p o w = 1 0 a now = \mathrm{one}(a), pow = 10 ^ a now=one(a),pow=10a 。
对于当前这一位,如果需要,那么 a n s = a n s ∗ p o w + n o w ans = ans * pow + now ans=ans∗pow+now 。再去更新 n o w now now 与 p o w pow pow : n o w = n o w ∗ p o w + n o w , p o w = p o w ∗ p o w now = now * pow + now, pow = pow * pow now=now∗pow+now,pow=pow∗pow ,同时 a = a / 2 a = a / 2 a=a/2 。
最后的 a n s ans ans 即是答案。
第二组
同样定义 f i f_i fi ,表示计算了 i i i 组之后的答案。有:
f i = ( 1 0 gcd ( a , b ) ∗ f i − 1 + 1 ) f_i = (10^{\gcd(a, b)} * f_{i - 1} + 1) fi=(10gcd(a,b)∗fi−1+1)
我们要求的便是 f b / gcd ( a , b ) f_{b / \gcd(a, b)} fb/gcd(a,b) 。
观察发现,这个式子与上一个长得挺像的,唯一区别就是 10 10 10 变成了 1 0 gcd ( a , b ) 10^{\gcd(a, b)} 10gcd(a,b) 。这倒也好办。只用在开始时把 p o w pow pow 设为 1 0 gcd ( a , b ) 10^{\gcd(a, b)} 10gcd(a,b) 。不过由于 gcd ( a , b ) \gcd(a, b) gcd(a,b) 很大,所以还要再写一个快速幂,这一组就这么解决了。
提交记录|快得飞起
ACode
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b, p, d;
int gcd(int a, int b) {if(b == 0) return a;return gcd(b, a % b);
}
int qpow(int x, int y) {int ans = 1;while(y) {if(y & 1) ans = (ans * x) % p;y >>= 1;x = (x * x) % p;}return ans;
}
int cal(int x, int y) {int now = 1, npow = qpow(10, y), ans = 0;while(x) {if(x & 1) ans = ((ans * npow) % p + now) % p;x >>= 1;now = ((now * npow) % p + now) % p;npow = (npow * npow) % p;}return ans;
}
void solve() {cin >> a >> b >> p;d = gcd(a, b);cout << cal(a, 1) * cal(b / d, d) % p << endl;return;
}
signed main() {cin.tie(0);cout.tie(0);int T = 1;while(T--) solve();return 0;
}
这篇关于[ARC050C] LCM 111 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!