f070 - 1. 韓信點兵 (HanXin)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了韓信點兵的問題，給定三個數字 a, b, c，代表士兵數可以被 a, b, c 分別除餘 0, 1, 2。要求找到滿足條件的最小士兵數量。題目實際上是求解一個同餘方程組，利用中國剩餘定理求解。

解題思路

題目可以轉化為求解以下同餘方程組： x ≡ 0 (mod a) x ≡ 1 (mod b) x ≡ 2 (mod c)

程式碼中，首先計算 k = a * c * e，然後分別計算 M1, M2, M3，它們分別是滿足 x ≡ 1 (mod a), x ≡ 1 (mod c), x ≡ 1 (mod e) 的最小正整數。接著，利用中國剩餘定理的公式 M = M1 * b + M2 * d + M3 * f 計算出解 M。最後，如果 M 大於 k，則對 k 取模，以得到最小正解。

複雜度分析

• 時間複雜度: O(max(a, b, c))，因為 while 迴圈的次數取決於 a, b, c 的大小。
• 空間複雜度: O(1)，程式碼只使用了常數個變數。

程式碼

#include <stdio.h>
int main(){
	long long int a,b,c,d,e,f;
	scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f);
	long long int k=a*c*e,m1=c*e,m2=a*e,m3=a*c,M1=m1,M2=m2,M3=m3;
	while(M1%a!=1)M1+=m1;
	while(M2%c!=1)M2+=m2;
	while(M3%e!=1)M3+=m3;
	long long int M=M1*b+M2*d+M3*f;
	if(M>k)M%=k;
	printf("%lld\n",M);
}