題目連結: https://zerojudge.tw/ShowProblem?problemid=c641
# 內容
暑假快到了，王老師打算買些糖果獎勵小朋友。
糖果屋有各式各樣的糖果。打算只買一種糖果。
王老師發現帶來的錢，
全買單價 3 元的糖果會剩下 2 元
全買單價 5 元的糖果會剩下 3 元
全買單價 7 元的糖果會剩下 5 元
你能推算出王老師最少帶多少錢嗎。
有若干組測資
每組測資有 2 行
第一行有 n 個數字 p 為各種糖果的單價，p 皆為質數。
第二行有 n 個數字 k 為剩餘的錢。
# 解題思路
經典的中國剩餘定理 (韓信點兵) 題目喔～～
# 程式碼
#include <iostream> | |
#define ll long long | |
using namespace std; | |
ll p[3],k[3]; | |
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){ | |
if(b==0) | |
d = a,x = 1,y = 0; | |
else{ | |
exgcd(b,a%b,d,y,x); | |
y-=(a/b)*x; | |
} | |
} | |
ll chinese(ll m[],ll a[]){ | |
ll M = 1,d,y,x = 0; | |
for(int i = 0;i<3;i++)M*=m[i]; | |
for(int i = 0;i<3;i++){ | |
ll w = M /m[i]; | |
exgcd(m[i],w,d,d,y); | |
x = (x+y*w*a[i])%M; | |
} | |
return (x+M)%M; | |
} | |
int main() | |
{ | |
while(cin>>p[0]){ | |
cin>>p[1]>>p[2]; | |
for(int i =0;i<3;i++)cin>>k[i]; | |
if(chinese(p,k)<=max(p[0],max(p[1],p[2]))) | |
cout<<p[0]*p[1]*p[2]+chinese(p,k)<<endl; | |
else | |
cout<<chinese(p,k)<<endl; | |
} | |
} |
