UVA10892 LCM Cardinality(gcd)

UVA10892 LCM Cardinality(gcd)

题意：给定整数n，问有多少组(a,b)使得lcm(a,b)=n，(3,4),(4,3)算作同一组。

本题n<=2e9，那么n^(0.5)<2e5. 以它为上界的双重循环大约有2e9的计算量，时间限制是2second，所以可以用暴力试试。

lcm(n,n)=n也算作一组。think about y=x^(0.5) curve. DETAL=(x+0.5)^(0.5)-x^(0.5)=0.5/[(x+0.5)^(0.5)+x^(0.5)]<1/[4*x(0.5)]<=0.25，所以int imax=sqrt((double)n) --> int  imax=sqrt(n+0.5).  另外，不要打错关键步骤，无限循环操作可能导致堆栈溢出，还以为自己数组开小了呢，在那里冥思苦想。

#include #include#includeusing namespace std;const int maxn=2e5;int fac[maxn],top;int gcd(int a,int b){ return b?gcd(b,a%b):a;}int lcm(int a,int b){ return a/gcd(a,b)*b;}int main(int argc, char *argv[]) { //freopen("cin.txt","r",stdin); int n; while(cin>>n&&n){ top=0; int i,j,imax=sqrt(n+0.5),ans=1; for(i=1;i<=imax;i++){ if(n%i==0){ fac[top++]=i; fac[top++]=n/i; } } if(fac[top-1]==fac[top-2])top--; //i*i=n for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。