洛谷 P12364 [蓝桥杯 2022 省 Python B] 寻找整数 C++题解
题解：洛谷 P12364 [蓝桥杯 2022 省 Python B] 寻找整数
题目传送门
一、题面描述
找到一个正整数n nn（0 ≤ n ≤ 10 17 0 \leq n \leq 10^{17}0≤n≤1017），要求满足题目表格中2 22到49 4949的余数，如下图：
二、思路
这题其实有一个很简单的方法——枚举。但是纯粹暴力绝对会超时，于是不难想到，可以使用逐步满足法。
只要一直加目前枚举到所有数的最小公倍数，直到满足下一个数的余数。
之所以加最小公倍数，是因为它可以整除前面的所有数，保持前面的余数不变。
即：
now ≡ 0 ( m o d x − 1 , x − 2 , … , 2 ) \text{now} \equiv 0 \pmod{x-1, x-2, \ldots, 2}now≡0(modx−1,x−2,…,2)
所以，先枚举除数x xx，接着一直加前面所有数的最小公倍数，一旦满足下一个除数的余数就跳出，然后再更新最小公倍数now \text{now}now，最后输出。
三、代码
#include<bits/stdc++.h>//万能头文件#defineintlonglong//宏定义：快速把int转换成long longusingnamespacestd;intmod[51]={0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46};//mod 数组存储余数intres,now=1;//结果，当前最小公倍数inlineintlcm(intx,inty){//最小公倍数函数（两数之积/最大公因数）returnx*y/__gcd(x,y);//__gcd为c++库函数}signedmain(){//signed=int（main函数必须为int类型）for(intx=2;x<=49;x++){//枚举除数while(mod[x]!=res%x){//一直加之前的最小公倍数，直到符合下一个条件res+=now;}now=lcm(now,x);//更新最小公倍数}printf("%lld",res);//输出答案return0;}时间复杂度
这段代码时间复杂度接近O ( n ) O(n)O(n)，而最坏情况是每一个内层循环x xx次，时间复杂度约为O ( n 2 ) O(n^2)O(n2)，不过由于正常数字余数分布随机，实际会更快。
答案
当然，这题有固定答案：2022040920220409 20220409202204092022040920220409。
所以，直接输出也行：
（但是，我们不应该提倡这种行为，应该认真地做代码）
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"2022040920220409";//答案return0;}