C. Neko does Maths(数论 二进制枚举因数)
题目链接：https://codeforces.com/contest/1152/problem/C
题目大意：给你a和b，然后让你找到一个k,使得a+k和b+k的lcm.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。学习网址：https://blog.csdn.net/yopilipala/article/details/89517933
具体思路：
AC代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 # define ll long long 4 # define inf 0x3f3f3f3f 5 const int maxn = 2e5+100; 6 vector<ll>sto; 7 void init(ll t) 8 { 9 ll tmp=t; 10 for(ll i=2; i*i<=tmp; i++) 11 { 12 while(t%i==0) 13 { 14 t/=i; 15 sto.push_back(i); 16 } 17 } 18 if(t!=1) 19 sto.push_back(t); 20 } 21 ll cal(int t) 22 { 23 ll ans=1ll; 24 int pos=0; 25 while(t) 26 { 27 if(t&1) 28 { 29 ans=ans*sto[pos]; 30 } 31 pos++; 32 t>>=1; 33 } 34 return ans; 35 } 36 int main() 37 { 38 ll a,b; 39 scanf("%lld %lld",&a,&b); 40 if(a==b) 41 { 42 printf("0\n"); 43 return 0; 44 } 45 if(a>b) 46 swap(a,b); 47 init(b-a); 48 int maxstate=(1<<(sto.size()))-1; 49 ll minn=(1ll<<60); 50 ll ans=(1ll<<60); 51 for(int i=1; i<=maxstate; i++) 52 { 53 ll tmp=cal(i); 54 ll t1=(a/tmp+1)*tmp;//注意是先除 55 ll t2=(b/tmp+1)*tmp; 56 ll w=t1*t2/__gcd(t1,t2); 57 if(w<=minn) 58 { 59 if(w<minn) 60 { 61 minn=w; 62 ans=t1; 63 } 64 else if(w==minn) 65 { 66 minn=w; 67 ans=min(ans,t1); 68 } 69 } 70 } 71 ll tmp=a*b/__gcd(a,b); 72 if(tmp<=minn) 73 { 74 minn=tmp; 75 ans=a; 76 } 77 printf("%lld\n",ans-a); 78 return 0; 79 }
更多精彩
