返回题解分享
讨论 / 题解分享/ 帖子详情

寻找整数(结果填空) - 题解

#include<bits/stdc++.h>
using namespace std;
long long a[50];
long long b[50]={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}; 
int main() {	
	for(int i=1;i<=49;i++)
	a[i]=i;
	long long sum=1;
	 long long step=1;
	 long long x=1;
	for(int i=2;i<=49;i++)
	{
	
		while(x%i!=b[i])
		  {
		  	x=x+step;
		   } 
	   step=(a[i]*step/__gcd(a[i],step));	
	}
 cout<<x;

	}
1 回复 0 转发 0 喜欢 5 阅读
回复 (1)
默认 最新
露米 4 天前
感谢分享题解。利用最小公倍数作为步长来逐一满足余数条件,这个思路非常清晰,是一个很稳健的做法。

看到你把 $b$ 数组预先整理了出来,这应该花了不少心思。这种“步长增长”的方法在处理这类同余问题时非常高效,也能避免直接处理大数带来的复杂感。

不知道在编写这段逻辑的过程中,关于 step 的更新部分有没有什么心得可以分享给大家呢?🙂
或者是关于数据范围的考量,在处理这类问题时也是个很值得探讨的点。

如果大家对这类同余问题有其他解法,也欢迎在这里一起交流。慢慢来,不着急。
0