UVa 11889 Benefit (数论)

本文主要是介绍UVa 11889 Benefit (数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa 11889 Benefit

---

题目大意:

给两个整数A和C,求最小的整数B使得lcm(A,B)=C.若无解,输出”NO SOLUTION”(不含引号).

题目分析:

显然可知,若C%A!=0,则无解.
对于有解的情况,如下

设$A=g*p_1\\B=g*p_2\\C=g*p_1*p_2$

要使$lcm(A,B)=C$,则$p_1与p_2$互质.
要使$B$尽可能小,因为$p_2=C/A$为定值,那么$g$需要尽可能小.
因为$A=g*p_1$是定值,那么$p_1$就要尽可能大.
所以题目转化为了在$p_1$与$p_2$互质的前提下,使得$p_1$尽可能大.

可以选择将$p_2$用唯一分解定理分解成多个质因数相乘.那么对于$p_2$所包含的质因数,$p_1$是不能选的,只能将其放在 g <script type="math/tex" id="MathJax-Element-2012">g</script>中.

代码:

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>using namespace std;const int maxn=10000000;
const int maxp=700000;int not_pri[maxn+1],pri[maxp+1],pcnt;void init(int n)
{for(int i=2;i<=n;i++) {if(!not_pri[i]) pri[pcnt++]=i;for(int j=0;j<pcnt&&1ll*pri[j]*i<=n;j++) {not_pri[pri[j]*i]=1;if(i%pri[j]==0) break;}}
}int main()
{init(maxn);int T;scanf("%d",&T);while(T--) {int A,C;scanf("%d%d",&A,&C);if(C%A) {printf("NO SOLUTION\n");continue;}int p=C/A,g=1;int m=sqrt(p),t=p;for(int i=0;pri[i]<=m&&t!=1;i++)if(t%pri[i]==0) {while(t%pri[i]==0) t/=pri[i];while(A%pri[i]==0) A/=pri[i],g*=pri[i];//因为B中有此质因数,故舍去,放在g中 }if(t>1) while(A%t==0) A/=t,g*=t;//t还剩下时,有且仅有一个大于√p,且t为素数,也判断需不需要舍去 printf("%d\n",p*g);}return 0;
}

这篇关于UVa 11889 Benefit (数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---