求公倍数的题，求解啊啊啊

kittennnn

最小的能够被1 到2023  整除的正数是多少？

由于答案很大，输出答案对 10的9次方+7 取模的结果

FishC

我们可以使用循环来解决这个问题。从1开始依次判断每个正整数是否能被1到2023整除，一旦找到一个能够被全部整除的数，就输出它并终止循环。

1. def find_smallest_multiple():
   
2.     i = 1
   
3.    
   
4.     while True:
   
5.         flag = True
   
6.         
   
7.         for j in range(1, 2024):
   
8.             if i % j != 0:
   
9.                 flag = False
   
10.                 break
    
11.         
    
12.         if flag:
    
13.             break
    
14.         
    
15.         i += 1
    
16.    
    
17.     return i % (10 ** 9 + 7)
    
18. 
    
19. result = find_smallest_multiple()
    
20. print(result)

复制代码

这段代码会逐个尝试判断1至2023之间的正整数，并查看是否能被1至2023整除。当找到一个满足条件的数时，循环结束并输出结果。注意我们用`flag`标志位来判断是否找到了符合要求的数。

由于答案可能非常大，我们使用取模操作将结果限制在10的9次方+7以内。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

jackz007

1. #include <stdio.h>
   
2. 
   
3. unsigned long long common(unsigned long long a , unsigned long long b)
   
4. {
   
5.         unsigned long long c , e , r = 0                                        ;
   
6.         if(0xffffffffffffffff / a >= b) {
   
7.                 e = a * b                                                       ;
   
8.                 while(b) {
   
9.                         c = a % b                                               ;
   
10.                         a = b                                                   ;
    
11.                         b = c                                                   ;
    
12.                 }
    
13.                 r = e / a                                                       ;
    
14.         }
    
15.         return r                                                                ;
    
16. }
    
17. 
    
18. int main(void)
    
19. {
    
20.         unsigned long long c , d , e                                            ;
    
21.         int f                                                                   ;
    
22.         for(c = d = 2 , f = 1 ; c < 2024 ; c ++) {
    
23.                 if((e = common(d , c))) {
    
24.                         d = e                                                   ;
    
25.                 } else {
    
26.                         fprintf(stderr , "【错误】：数据溢出，c = %I64u\n" , c) ;
    
27.                         f = 0                                                   ;
    
28.                         break                                                   ;
    
29.                 }
    
30.         }
    
31.         if(f) printf("%I64u\n" , d)                                             ;
    
32. }

复制代码

        编译、运行实况：

1. D:\[exercise]\C>g++ -static -o x x.c
   
2. 
   
3. D:\[exercise]\C>x
   
4. 【错误】：数据溢出，c = 44
   
5. 
   
6. D:\[exercise]\C>

复制代码

        结果显示，在采用 64 位整型数的情况下，不要说到 2023，到 44 的时候，数据就已经溢出了。因此，本例不适合用 C / C++ 解题。
        我们知道，Python 的整型数没有大小限制，所以，可以考虑用 Python 解决：

1. def common(a , b) :
   
2.     e = a * b
   
3.     while b :
   
4.         a , b = b , a % b
   
5.     return e // a
   
6. 
   
7. d , e = 2 , 2024
   
8. for c in range(2 , e) :
   
9.     d = common(d , c)        
   
10. print(d)

复制代码

        运行实况：

1. D:\[exercise]\Python>python x.py
   
2. 1227762956206264118623582541141429549187405177671946464234060731173734645254182863376194152615540505727280653219993317703690524447072610762067793783389005080071796734974865735024986021773726186055458284951748244494933118245578743488914855761878373488868135308841351284532341908809292500010956012208958938141828554364557040594646657783559448232174265632350285186465097411385335942800873708199800202908492724165372047120049528852902328840849252383573180295509547022528099248913962683339793793394550081062639422036767297274851821052696199703915096818519708383217155227462807171855362054148439780401358852626710718548830459614712023730554202373301584134686655430931771332369748911981895426450530517669134338114943553709392259149091137078884995327967573921281316017539167265196705242563435197494576760930221836117819851391468452932981303604385960824026393965398955132764499684480000
   
3. 
   
4. D:\[exercise]\Python>

复制代码

zhangjinxuan

你可以试试求出答案的分解质因数：

1. #include <stdio.h>
   
2. 
   
3. #define max(a, b) (a > b ? a : b)
   
4. 
   
5. int maxfact[2024];
   
6. const int n = 2023;
   
7. 
   
8. int main() {
   
9.         for (int i = 1; i <= n; ++i) {
   
10.                 int tmp = i;
    
11.                 for (int j = 2; j * j <= tmp; ++j) {
    
12.                         int tot = 0;
    
13.                         while (tmp % j == 0) {
    
14.                                 ++tot;
    
15.                                 tmp /= j;
    
16.                         }
    
17.                         maxfact[j] = max(maxfact[j], tot);
    
18.                 }
    
19.                 if (tmp) maxfact[tmp] = max(maxfact[tmp], 1);
    
20.         }
    
21.         long long res = 1;
    
22.         for (int i = 1; i <= n; ++i) {
    
23.                 while (maxfact[i]--) {
    
24.                         (res *= i) %= 1000000007;
    
25.                 }
    
26.         }
    
27.         printf("%lld\n", res);
    
28.         return 0;
    
29. }

复制代码

答案 61465412，与楼上结果一致。