Codeforces 1203C的公共因子（gcd）问题，如何求解长尾词的公共因子？

本文共计525个文字，预计阅读时间需要3分钟。

题目链接：https://codeforces.com/problemset/problem/1203/C

题目要求：给定一个数列，求该数列所有数的最大公因数的个数。

简单来说，就是求给定数列中所有数最大的公约数的数量。

分类讨论：div2、div3

放弃说的太多，直接说结果。

训练题：求所有数的最大公因数的个数。

题目链接：codeforces.com/problemset/problem/1203/C

求给定数列所有数的公因数个数

没什么好说的，其实就是求所有数最大公因数的因数个数。div2上分div3掉分，丢人说的就是我吧。教训就是大数的因数很多所以能少算一点是一点，别的花里胡哨的操作没有这个方便而且省的多。

代码上面那个是我为了逃过tle去看的更相减损术求gcd，道理来说比较快但完全没有拯救我的死脑筋。。。也没必要用，摆在这就当一个扩展。

#include<iostream> #include<cstdio> #include<set> #include<stdio.h> #include<string.h> #include<math.h> #include<vector> #include<stdlib.h> #include<queue> #include<algorithm> #include<map> #include<stack> using namespace std; long long qgcd(long long a,long long b) { if(a==0) { return b; } if(b==0) { return a; } if(!(a&1)&&!(b&1)) { return qgcd(a>>1,b>>1)<<1; } else if(!(b&1)) { return qgcd(a,b>>1); } else if(!(a&1)) { return qgcd(a>>1,b); } else { return qgcd(abs(a-b),min(a,b)); } } long long gcd(long long a,long long b) { return b?gcd(b,a%b):a; } long long a[400005]; int main() { int n; scanf("%d",&n); long long ans=-1; long long a; while(n--) { scanf("%I64d",&a); if(ans==-1) { ans=a; } else { ans=gcd(ans,a); } } int s=0; for(long long i=1;i<=sqrt(ans);i++) { if(ans%i==0) { if(ans/i==i)//如果是最大公因数的开根号，那就减去一个避免同一个因数重复统计 { s--; } s+=2; } } printf("%d\n",s); return 0; }