Neko does Maths CodeForces - 1152C 数论欧几里得

　　题目大意：给两个正整数a,b，找到一个非负整数k使得，a+k和b+k的最小公倍数最小，如果有多个k使得最小公倍数最小的话，输出最小的k。

　　首先让b>a，由lcm（a,b)=a*b/gcd(a,b)，可以得出如果b%a==0，那么它们的最小公倍数就是b，此时的k就等于0。但如果b%a!=0的话，我们设g=gcd(a+k,b+k)，那么就是有a+k=q1*g,b+k=q2*g，两者做差，那么b-a=(q2-q1)*g,由此我们可以知道g是b-a的因子。知道这个消息有什么用呢，我们可以在√(b-a) 内枚举g，这样g就是已知量了，我们设q3=(b-a)/g的话，q2=q1+q3,由lcm(a+k,b+k）=(a+k)*(b+k)/gcd(a+k,b+k)，就有lcm(a+k,b+k)=q1*q2*g，那么lcm(a+k,b+k)=q1*(q1+q3)*g,只剩下一个未知量q1，而且要让lcm最小，q1也得最小，而q1=（a+k）/g,所以要让q1最小其实就是找一个最小的k使得(a+k)%g==0，那么k=(g-a%g)%g。这样的话枚举g，相应的k也就是出来了，再更新答案就好.

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 int a,b,k;

 ll ans;

 ll lcm(ll a,ll b){

     return a*b/__gcd(a,b);

 }

 void solve(int g)

 {

     int nk=(g-a%g)%g;

     ll nans=lcm(1ll*(a+nk),1ll*(b+nk));

     if(nans<ans||(nans==ans&&nk<k))

         k=nk,ans=nans;

 }

 int main()

 {

     scanf("%d%d",&a,&b);

     if(a>b){

         ll t=a;a=b;b=t;

     }

     if(b%a==)

     {

         printf("0\n");

         return ;;

     }

     int dis=b-a;

     k=;

     ans=lcm(a,b);

     for(int i=;i*i<=dis;i++)

     {

         if(dis%i==)

         {

             solve(i);

             solve(dis/i);

         }

     }

     printf("%d\n",k);

     return ;

 }

数论推推推

巴特西

Neko does Maths CodeForces - 1152C 数论欧几里得

最新文章

热门文章