題目描述：

第一行和第二行輸入8個(gè)數(shù)字，對應(yīng)每一位第二行都小于第一行，求最小的值$x$令$x$對第一行每一位取余后等于第二行$(x不小于第一行的每個(gè)數(shù))$

題目分析：

首先有式子$x$%$a=b$,$x$%$c=d$,先設(shè)第一個(gè)滿足條件的$x$為$x1$對于每個(gè)滿足題意的$x$，都有$x=n?LCM(a,c)+x1$，$LCM(a,c)$為$a$和$c$的最小公倍數(shù)，這點(diǎn)可以自行證明。此時(shí)令$m=LCM(a,c)$。

隨后，若引入一個(gè)新的$e,f$有$x$%$e=f$，則$x$要在滿足$x=n?LCM(a,c)+x1$的情況下查找滿足新式子的最小$x2$，隨后更新$m$，因?yàn)橹鬂M足的$x$與$x2$的差值又要滿足被$a,c,e$整除，因此就要將$m$更新為$m=LCM(m,e)$，以此類推，求得最后一個(gè)滿足的最小$x$即為答案。

復(fù)雜度大概是ans除一個(gè)階乘吧，不太好算，但是比暴力枚舉快一些

代碼：

#include<iostream> #include<algorithm> #include<stdio.h> #include<string> #include<string.h> #include<math.h> typedef long long ll;using namespace std;int m, n; struct P {int a, b; }p[8];bool cmp(P a, P b) {return a.a < b.a; }int gcd(int a, int b) {//gcd模板，求最大公約數(shù)return (b ? gcd(b, a % b) : a); }int lcm(int a, int b) {//根據(jù)gcd求最小公倍數(shù)return a / gcd(a, b) * b; }int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//c++操作，不用管他for (int i = 0; i < 8; i++) cin >> p[i].a;for (int i = 0; i < 8; i++) cin >> p[i].b;//兩行輸入m = p[0].a, n = p[0].b + p[0].a; int j;//初始化，此時(shí)m每次加第一個(gè)a，n為滿足第一對的最小值for (int i = 1; i < 8; i++) {for (j = n; ; j += m) {//j被初始化為當(dāng)前最小值每次加mif (j % p[i].a == p[i].b && j % p[i - 1].a == p[i - 1].b) {//判斷成立，更新n和m，退出當(dāng)前層循環(huán)n = j, m = lcm(m, p[i].a); break;}}}cout << n << endl;return 0; } /* 2 3 5 7 11 13 17 19 1 2 4 6 10 12 16 18 */

總結(jié)

以上是生活随笔為你收集整理的一道GCD LCM题目题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。