企业官网建设流程全解析

专注旅游网站网站开发,重庆市建设公共资源交易中心网站首页,做问卷用哪个网站,网站的类型及特点1390: 四因数思路一#xff1a;枚举我们可以遍历数组 nums 中的每个元素#xff0c;依次判断这些元素是否恰好有四个因数。对于任一元素 x#xff0c;我们可以用类似质数判定的方法得到它的因数个数#xff0c;其本质为#xff1a;如果整数 x 有因数 y#xff0c;那么也必…1390: 四因数思路一枚举我们可以遍历数组 nums 中的每个元素依次判断这些元素是否恰好有四个因数。对于任一元素 x我们可以用类似质数判定的方法得到它的因数个数其本质为如果整数 x 有因数 y那么也必有因数 x/y并且 y 和 x/y 中至少有一个不大于 sqrt(x)。这样我们只需要在 [1, sqrt(x)] 的区间内枚举可能为整数 x 的因数 y并通过 x/y 得到整数 x 的其它因数。如果 x 恰好有四个因数我们就将其因数之和累加到答案中。class Solution { public: int sumFourDivisors(vectorint nums) { int ans0; for(int x:nums){ int cnt0,total0; for(int i1;isqrt(x);i){ int jx/i; if(j*ix){ if(ji){ cnt; totali; } else{ cnt2; totalij; } } } if(cnt4) anstotal; } return ans; } };进阶埃拉托斯特尼筛法埃氏筛class Solution { public: int sumFourDivisors(vectorint nums) { // C 是数组 nums 元素的上限C3 是 C 的立方根 int C 100000, C3 46; vectorint isprime(C 1, 1); vectorint primes; // 埃拉托斯特尼筛法 for (int i 2; i C; i) { if (isprime[i]) { primes.push_back(i); } for (int j i i; j C; j i) { isprime[j] 0; } } // 通过质数表构造出所有的四因数 unordered_mapint, int factor4; for (int prime: primes) { if (prime C3) { factor4[prime * prime * prime] 1 prime prime * prime prime * prime * prime; } } for (int i 0; i primes.size(); i) { for (int j i 1; j primes.size(); j) { if (primes[i] C / primes[j]) { factor4[primes[i] * primes[j]] 1 primes[i] primes[j] primes[i] * primes[j]; } else { break; } } } int ans 0; for (int num: nums) { if (factor4.count(num)) { ans factor4[num]; } } return ans; } };