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 <iostream>
#include<cstdio>
#include<cmath>
using 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<top;i++){
      for(j=i+1;j<top;j++){
        if(lcm(fac[i],fac[j])==n){
          ans++;
        }
      }
    }
    printf("%d %d\n",n,ans);
  }
  return 0;
}