Codeforces 1203C Common Divisors(gcd)

发布时间：2020-12-16 09:19:56 所属栏目：百科来源：网络整理

导读：题目链接：https://codeforces.com/problemset/problem/1203/C 求给定数列所有数的公因数个数没什么好说的，其实就是求所有数最大公因数的因数个数。div2上分div3掉分，丢人说的就是我吧。教训就是大数的因数很多所以能少算一点是一点，别的花里胡哨的操作

题目链接：https://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("%dn",s);
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!