表白网站制作生成器,亚马逊网站类型,营销型网站建设目的,沧州易淘网络科技有限公司题干#xff1a;
给出a,b1e9#xff0c;你要找到最小的k使得lcm(ak,bk)尽可能小#xff0c;如果有多个k给出同样的最小公倍数#xff0c;输出最小的一个k。
解题报告#xff1a;
因为题目中k太多了#xff0c;先化简一下公式#xff0c;假设ab #xff0c;则…题干
给出a,b1e9你要找到最小的k使得lcm(ak,bk)尽可能小如果有多个k给出同样的最小公倍数输出最小的一个k。
解题报告
因为题目中k太多了先化简一下公式假设ab 则gcd(ak,bk) gcd(ak,ab)
下面给出一个简单证明
zgcd(ak,bk); 所以:(ak)%z0,(bk)%z0; (ak)%z(bk)%z; a%zk%zb%zk%z;
故 (a-b)%z0;
还有个一般化的结论 gcd(a,a) gcd(a,a) gcd(a,b) gcd(a,a-b)(ab) gcd(a,b) gcd(b,a-b)(ab)
所以公式可以化为
lcm(ak,bk) (ak)*(bk) / gcd(ak,bk). 要使得lcm(ak,bk)最小则需要gcd(ak,bk)最大
因此只需要枚举(a-b)的因子将ak凑至存在该因子fac即ak是fac的倍数求出那个最小的k即k fac-a%fac取lcm最小值即可。
至于为什么kfac-a%fac呢下面给出简要证明
这是因为首先kfac因为假设kfac有上述条件成立则总可以通过k-fac的操作使得k变小且原式依旧成立且k是在这个条件下是唯一的这个很显然不解释了所以在模fac的意义下肯定有ak0(mod fac)因此kfac-a%fac
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
ll a,b;
vectorll vv;
void solve(ll x) {//求出x的所有因子 for(ll i 1; i*ix; i) {if(x%i 0) {vv.pb(i);if(i*i!x) vv.pb(x/i);}}
}
ll lcm(ll a,ll b) {return a*b/__gcd(a,b);
}
int main()
{cinab;if(a b) swap(a,b);//保证abll tmp a-b,minn lcm(a,b),ans0;solve(tmp);int up vv.size();for(int i 0; iup; i) {ll k vv[i] - a%vv[i];if(lcm(ak,bk) minn) {minn lcm(ak,bk);ans k;}} cout ans endl;return 0 ;
}
