题意：
输入正整数n，统计有多少a<=b满足lcm(a,b)=n。输出n以及满足条件的整数对数。
思路：
根据素因子分解求最小公倍数的算法，可以的得出这样的结论。如果对一个数进行素因子分解，那么思路就明显了
1. 设n=lcm(a,b)=(p1^r1)*(p2^r2)*(p3^r3)…(pm^rm)
又设a=(p1^a1)*(p2^a2)*(p3^a3)…(pm^am),b=(p1^b1)*(p2^b2)*(p3^b3)…(pm^bm)
则由lcm的定义有ri=max{ai,bi}
所以对于每个ri，ai和bi中至少有一个要取ri
2. 对于ai取ri的情况，bi可以取[0,ri-1]的任意整数，这有ri种情况；bi取ri的情况同样是ri种。最后加上ai和bi都取ri的情况，共有(2*ri+1)种情况
3. 最后，由于这么考虑把(a,b)和(b,a)算重复了，但(n,n)的情况只算了一遍，所以最后要ans=(ans+1)/2=ans/2+1（因为ans是奇数）
4. 优化：只考虑√n范围内的质数
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <cmath> 5 using namespace std; 6 const int maxx=100005; 7 int fac[maxx]; 8 int num[maxx],prime[maxx],p[maxx]; 9 int cnt,k; 10 void isprime() 11 { 12 memset(prime,true,sizeof(prime)); 13 k=0; 14 for(int i=2;i<maxx;i++) 15 { 16 if(prime[i]) 17 { 18 p[k++]=i; 19 for(int j=i+i;j<maxx;j+=i) 20 prime[i]=false; 21 } 22 } 23 } 24 void gao(long long n) 25 { 26 cnt=0; 27 isprime(); 28 for(int i=0;i<k;i++) 29 if(n%p[i]==0) 30 { 31 int a=0; 32 while(n%p[i]==0) 33 { 34 n/=p[i]; 35 a++; 36 } 37 fac[cnt]=p[i]; 38 num[cnt++]=a; 39 } 40 if(n>1) 41 { 42 fac[cnt]=n; 43 num[cnt++]=1; 44 } 45 } 46 int main() 47 { 48 long long n; 49 while(cin >> n) 50 { 51 if(n==0) 52 break; 53 gao(n); 54 long long ans=1; 55 for(int i=0;i<cnt;i++) 56 ans*=num[i]*2+1; 57 ans=(ans+1)/2; 58 cout << n << " " << ans<< endl; 59 } 60 return 0; 61 }