模余数最大公倍数
- 模余数
- 题:
模余数
- 如果a%m=b,则(a+m*k)%=b。
- 对m求模,余数为b的整数b+m*k
题:
若干人,3001人为一排,余1人
4001人为一排,余2人
4999人为一排,余3人
求人数的最小值。
#include <iostream>
typedef long long ll;
using namespace std;
//最大公约数 展转相除法
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b);
}
//最小公倍数
ll lcm(ll a,ll b){
return a*b/gcd(a,b);
}
int main(){
int a=3001,a1=1;
int b=4001,b1=2;
int c=4999,c1=3;
ll x=a1;
while(x%b!=b1) x+=a;
while(x%c!=c1) x+=lcm(a,b);
cout <<x<<endl;
return 0;
}