本文共 1586 字，大约阅读时间需要 5 分钟。
题目链接：，题目大意：给你两个数 n 和 m，问你有多少对正整数对最大公约数是n，最小公倍数是m。
因为1 <= n, m <= 10000000000，暴力法肯定超时的，比赛时我也想到了把 n 和 m 分解开，质因数和对应的指数存放在 map 中，思路是正确的，可没想到在一些细节问题上没考虑周全，在没有判断 n 和 m 是否互质前就盲目地把它们进行分解，结果当然是wa了数遍，亏我还在苦苦思索是不是思路出错了，直至今天与文聪讨论时才发现这个瑕疵。用朴素的分解方法已经能够在时限范围内过了，然后我用素数筛法生成素数后再去分解 n 和 m 时明显快了很多：
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std;12 typedef long long LL;13 const LL INF= 0x3fffffff;14 const LL maxn= 100005;15 16 bool vis[maxn];17 int prime_num;18 LL prime[10004];19 int Init(LL n= maxn)20 {21 int c= 0;22 for(LL i=2; i<=n; ++i)23 if(!vis[i]){24 prime[++c]= i;25 for(LL j= i*i; j<=n; j+=i) vis[j]= 1;26 }27 return prime_num= c;28 }29 30 void factor(LL n, map &m)31 {32 LL tmp= sqrt(n+0.5), i;33 for(i=1; i<=prime_num && prime[i]<=tmp; ++i)34 if(n%prime[i]==0){35 int num= 1;36 while((n/=prime[i])%prime[i]==0) ++num;37 m[prime[i]]= num;38 }39 if(n!=1) m[n]= 1;40 }41 42 int main()43 {44 int t;45 LL x,y;46 scanf("%d",&t);47 Init();48 while(t--){49 scanf("%lld%lld",&x,&y);50 if(x==y){51 puts("1");52 continue;53 }54 if(x>y) swap(x,y);55 if(y%x) {56 puts("0");57 continue;58 }59 map m1,m2;60 factor(x,m1);61 factor(y,m2);62 map ::iterator it;63 64 LL ans= 1;65 for(it= m2.begin(); it!=m2.end(); ++it)66 if(it->second != m1[it->first]) ans<<=1;67 printf("%lld\n",ans>>1);68 }69 return 0;70 }
转载于:https://www.cnblogs.com/Newdawn/p/4345521.html
