我一直相信这道题有十分巧妙的解法的，去搜了好多题解发现有的太过玄妙不能领会。
最简单的就是枚举n的所有约数，然后二重循环找lcm(a, b) = n的个数
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 using namespace std; 5 6 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 7 8 int lcm(int a, int b) { return a / gcd(a, b) * b; } 9 10 int main() 11 { 12 //freopen("in.txt", "r", stdin); 13 14 int n; 15 while(scanf("%d", &n) == 1 && n) 16 { 17 vector<int> a; 18 for(int i = 1; i * i <= n; i++) if(n % i == 0) 19 { 20 if(i * i == n) a.push_back(i); 21 else { a.push_back(i); a.push_back(n / i); } 22 } 23 sort(a.begin(), a.end()); 24 int num = a.size(), ans = 0; 25 for(int i = 0; i < num; i++) 26 for(int j = i; j < num; j++) 27 if(lcm(a[i], a[j]) == n) 28 ans++; 29 printf("%d %d ", n, ans); 30 } 31 32 return 0; 33 }
后来在网上找到一种这样的解法，赞叹其精妙，效率要高很多。
1 #include <cstdio> 2 #include <cmath> 3 4 const int maxn = sqrt(2000000000 + 0.5); 5 bool vis[maxn + 10]; 6 int prime[5000], pcnt = 0, e[5000], cnt; 7 int suffix[5000]; 8 int f(int n) 9 { 10 if(n == cnt) return 1; 11 return e[n] * suffix[n+1] + f(n + 1); 12 } 13 14 int main() 15 { 16 int m = sqrt(maxn +0.5); 17 for(int i = 2; i <= m; i++) if(!vis[i]) 18 for(int j = i*i; j <= maxn; j += i) vis[j] = true; 19 for(int i = 2; i <= maxn; i++) if(!vis[i]) prime[pcnt++] = i; 20 //printf("%d ", pcnt); 21 22 int n; 23 while(scanf("%d", &n) == 1 && n) 24 { 25 printf("%d ", n); 26 cnt = 0; 27 for(int i = 0; i < pcnt && n > 1; i++) if(n % prime[i] == 0) 28 { 29 e[cnt] = 0; 30 while(n % prime[i] == 0) { e[cnt]++; n /= prime[i]; } 31 cnt++; 32 } 33 if(n > 1) e[cnt++] = 1; suffix[cnt] = 1; 34 for(int i = cnt - 1; i >= 0; i--) 35 suffix[i] = suffix[i + 1] * (e[i]*2+1);//后缀的乘积 36 printf("%d ", f(0)); 37 } 38 39 return 0; 40 }