思路：a，b，n都能分解成素数乘积。A=p1a1…；B=p1b1…；N=p1c1… 若n为lcm(a,b)，则ci=max(ai,bi)。所以就有两种情况： 1、ci=ai：则bi可以从0取到ci，共ci+1种情况； 2、同理，对于bi=ci，ai也有ci+1种情况。 共2(ci+1)-1种情况（ai=bi被计算两遍） 所以我们只需要(∏(2ci+1)+1)/2即为结果。（可以用2来试一试就明白了） 然而，第一次maxn开1e6 WA，同时记得v开到1e7，素数开到1e6就可以；第二次卡空间，最后在筛素数的时候，把v改成bool就ok了 AC代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=1e7+10; int prime[maxn/10]; bool v[maxn];//合数标记 int prime_num=0; void find_primes(int n) { memset(v,false,sizeof(v)); for(int i=2;i<=n;i++){ if(v[i]) continue; prime[++prime_num]=i; //优化：从x^2开始,(x+1)*x...到N/x*x结束,标记为合数即可 for(int j=i;j<=n/i;j++) v[i*j]=true; } } int m; LL ans; void find_c(LL n) { m=0;ans=1; for(int i=1;i<=prime_num;i++){ if(n<prime[i]) break; if(n%prime[i]==0){ LL tot=1;n/=prime[i]; while(n%prime[i]==0) n/=prime[i],tot++; ++m; ans*=(2*tot+1); } } if(n>1) ans*=3; } int main() { find_primes(maxn-5); int t;cin>>t; for(int j=1;j<=t;j++){ LL n;cin>>n; find_c(n); cout<<"Case "<<j<<": "<<(ans+1)/2<<endl; } }