零、写在前面
这是打卡的第十二天，主要内容在
《算法零基础100讲》(第12讲) 因子和
https://blog.csdn.net/WhereIsHeroFrom/article/details/120875424
一、主要知识点
一个数n的因子和
对于n我们进行相应的因式分解 
那么我们很容易得到n的所有约数是a1取0.....a1,a2取0....a2，a3取0.....a3得到积一共有(a1+1)(a2+1)(a3+1)个结果
那么S(n) = (1 + p^1+p^2 + ... p^a1)(1+q^1+...q^a2)......
每个括号里面分别对应a1+1个,a2+1....个元素，拆开刚好对应所有的约数。
那么S(n)很容易看出来每个括号里都是一个等比数列，所以一共就是
二、课后习题详解
四因子数
The number of divisors(约数) about Humble Numbershttp://acm.hdu.edu.cn/showproblem.php?pid=1492
http://acm.hdu.edu.cn/showproblem.php?pid=1492
思路
题目说了一共包含四个因子，那么只能是
两个质因子的乘积
是一个质因子的三次方两种情况。
对于质数我们可以用之前学过的线性筛进行筛选，然后就行判定求解。
#define maxn 50001 bool f[maxn]; int primes[maxn]; void ethPrime(){ // memset(f,1,sizeof(f)); primes[0] =0; for(int i = 2;i < maxn; ++i){ if(f[i]) primes[++primes[0]] = i; for(int j = 1;j <= primes[0] && primes[j] * i < maxn;j++){ f[i*primes[j]] = 0; if(!i % primes[j] )break; } } } int sumFourDivisors(int* nums, int numsSize){ int ans = 0; ethPrime(); for(int i = 0;i < numsSize;i++) for(int j = 1;j<= primes[0]&&primes[j] <nums[i];++j) if(!(nums[i] % primes[j]))//找到第一个质因子 if(f[nums[i] / primes[j]] && primes[j]*primes[j] != nums[i]){//是否满足第一种情况 ans += (primes[j] +1)*(nums[i] / primes[j] +1); break; } else if((long long )primes[j]*primes[j]*primes[j] == nums[i]){//是否满足第二种情况 ans += (pow(primes[j],4) - 1)/(primes[j] - 1); break; } else break;//不满足两种情况，及时返回 return ans; }
结果分析
在代码中及时返回减少了一些时间达到了76ms，但是，，，我不满意。。。
思路2
打表yyds，但是我尝试了一下，页面卡死，提交不了？？？是被制裁了？那不让我打表进去，我让机器进行打表就好了，我用一个数组生成所有的数据，查表就行了。
#define maxn 50001 bool f[maxn]; int primes[maxn]; int siyuanzu[100001] = {0}; void init(){//生成所有的变量对应的值 for(int i = 1;i <= primes[0] && primes[i]*primes[i]*primes[i] < 100001;i++) siyuanzu[primes[i]*primes[i]*primes[i]] = (pow(primes[i],4) - 1)/(primes[i] - 1); for(int i = 1;i <= primes[0];i++) for(int j = 1;i != j && j <= primes[0] && (long long)primes[i]*primes[j] < 100001;j++) siyuanzu[primes[i]*primes[j]] =(primes[i] + 1)*(primes[j] + 1); } void ethPrime(){//埃氏筛 memset(f,1,sizeof(f)); primes[0] = 0; for(int i = 2;i < maxn;++i){ if(f[i]){ primes[++primes[0]] = i; for(long long j = (long long)i*i;j < maxn;j+=i) f[j] = 0; } } } /* void ethPrime(){ //欧拉筛 memset(f,1,sizeof(f)); primes[0] =0; for(int i = 2;i < maxn; ++i){ if(f[i]) primes[++primes[0]] = i; for(int j = 1;j <= primes[0] && primes[j] * i < maxn;j++){ f[i*primes[j]] = 0; if(!i % primes[j] )break; } } }*/ int sumFourDivisors(int* nums, int numsSize){ int ans = 0; ethPrime(); init(); for(int i = 0;i < numsSize;++i){ printf("%d",siyuanzu[nums[i]]); ans += siyuanzu[nums[i]]; } return ans; }
结果分析
那就这样吧
课后总结
linux环境高级编程好高级，高级的我写作业写了300行还没写完┭┮﹏┭┮，写完了过两天写篇文章介绍一下这个高级编程-.-
