文章目录

题意题解代码

题目连接 vj or cf

题意

统计一组数公约数的个数

题解

求出这一组数里的最大公约数, 从 1 遍历到 这个最大公约数, 统计有几个数能被最大公约数整除即为所求

当然, 这样超时了 … 我们需要优化一下

可以想象一下, 以 sqrt( maxGcd ) 为分界线, 那么就是说这个两边对应的数字都是 i 的倍数, 比如, 比如 maxGcd = 100, sqrt() = 10, 那么, 约数如下: 1 2 4 5 |10| 20 25 50 100 sqrt() 左边对应的每一个数字, 右边都会有一个数字为maxGcd/左边数字 … 当然, sqrt() 是双精度浮点型, 并且每个数被开平方并不一定是刚好是整数, 如果刚好是整数的话, 它自身就是分界线, 不会有对应的, 而我们算的是对应的, 统计到了一半, 直接乘2翻倍, 所以多加了一次, 这时候需要最后减一. 如果是小数的话, 这个小数是分界线, 所以左边有数一定对应右边一个, 这个时候尽管加一,最后翻倍即可

由此, 我们可以缩小一下遍历的范围到 sqrt( maxGcd ), 最后还需要判断一下 这个根号 到底是加一还是加二, 见图

例如, maxGcd = 9 -> sqrt() = 3.4 maxGcd = 10 -> sqrt() = 3.333 maxGcd = 12 -> sqrt() =

第一种情况, 3 的时候就加一次, 第二种情况, 3 的时候不加, 第三种情况, 3 的时候加两次

考虑一下, emm … 这个优化很巧妙

get 新技能, algorithum 里有内置的求 gcd 的函数, __gcd() 注意两个下划线, 可以求 int, long long, 但是两个参数类型要对应

代码

#include <bits/stdc++.h> using namespace std; #define rg register #define sc scanf #define pf printf typedef long long ll; const ll MAXN = 4e5+100; //ll gcd ( ll a, ll b ) { // ll r ; // while ( b ) { r = a%b, a = b, b = r; } return a ; //} ll n, a[MAXN]; int main ( ) { // freopen( "F:\\in\\.txt" , "r" , stdin ); sc( "%lld", &n ); sc( "%lld", &a[1] ); // cin >> n; // cin >> a[1]; ll maxGcd = a[1]; for ( ll i = 2; i <= n; ++i ) { sc( "%lld", &a[i] ); // cin >> a[i]; maxGcd = __gcd( a[i], maxGcd ); } ll sum = 0; double len = sqrt( maxGcd ); for ( ll i = 1; i <= len; ++i ) if ( maxGcd%i==0 ) sum ++; sum *= 2; if ( len == (ll)len ) sum--; pf( "%lld\n", sum ); return 0 ; }