搞定B题！常见公约数（Codeforces）：数论算法基本定理和唯一分解定理模板
最编程
2024-02-04 09:19:09
...
Output
4
求一组数的共同因数的数目。
看数据，暴力一个一个看肯定超时。脑子跟猪一样，看完这个题，我的第一反应，竟然只知道这些因数一定小于最小的数（废话）。结果思维一直限制，绕在里面出不来。
打了一年了，自己还是....唉，努力训练吧，上题解。
以下两种解法都需要求出这组数的最大公因数。为什么呢，找到总的最大公因数N，那么剩下的公因数一定小于它。竟然这组数可以整除N，那么也一定可以整除N的因数。
接下来的工作，就是找N的因数个数。
解法一：直接找，但是不能暴力一个一个for，还是会超时。要知道，一个数N的因数，以sqrt（N）为分界线，一半在左，一半在右。所以我们只需求出<sqrt(n)的部分ans，
ans*2，然后对sqrt(N)特判一下，看看，是否(int)sqrt(N)*(int)sqrt(N)==N.
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int maxn=4e5+10; ll tot=0; ll a[maxn]; ll cha[maxn]; ll b[maxn]; int main() { ll n; while(cin>>n) { for(int i=0;i<n;i++) scanf("%lld",&a[i]); ll k=a[0]; for(int i=1;i<n;i++) k=__gcd(k,a[i]); if(k==1) { printf("1\n"); continue; } double mid=sqrt(k); ll ans=0; for(int i=1;i<mid;i++) { if(k%i==0) ans++; } ans*=2; if((int)mid*mid==k) ans++; cout<<ans<<endl; } }
解法二：数论。算术基本定理（摘自****）：
所以对N进行分解：
ll ans=1; for(ll i=2;i*i<=t;i++) { if(t%i==0) { ll cnt=0; while(t%i==0) { t=t/i; cnt++; } ans=ans*(cnt+1); } } if(t>1)//别忘了加 ans*=2;
//算是唯一分解定理的一个模板
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdio> using namespace std; typedef long long ll; const int maxn=4e5+10; ll a[maxn]; int main() { ll n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; ll t=a[0]; for(int i=1;i<n;i++) t=__gcd(t,a[i]); if(t==1) cout<<"1"<<endl; else { ll ans=1; for(ll i=2;i*i<=t;i++) { if(t%i==0) { ll cnt=0; while(t%i==0) { t=t/i; cnt++; } ans=ans*(cnt+1); } } if(t>1) ans*=2; cout<<ans<<endl; } }
不多说，接着训练！不给自己的acm生涯留遗憾！