Common Divisors

Common DivisorsCodeForces - 1203C题目要我们求数组中所有元素的公约数的数量看到公约数让我想到了最大公约数__gcd,然后就是数据量太大了如果是直接求每个数组的约束统计计数会爆其实想一想所有公约数的数量就是最大公约数的约数数量只要是最大公约数了那么肯定是数组所有元素共同的计算公约数时不要忘了a%b是两个约数要分辨计算最后发现__gcd的数据是错的他不适配long long类型的数据那我就手搓一个gcd函数功能一样的就可以了速度不慢可以优先使用不一定要用内置的函数。#includebits/stdc.h#defineintlonglongusingnamespacestd;inta[400005];intcnt0;intgcd(inta,intb){while(b){intta%b;ab;bt;}returna;}voidcheck(intx){for(inti1;i*ix;i){if(x%i0){if(ix/i){cnt;}else{cnt2;}}}}signedmain(){intn;cinn;intsum0;for(inti1;in;i){cina[i];sumgcd(a[i],sum);}check(sum);coutcntendl;return0;}