零、写在前面
这是打卡的第十一天，主要内容在
《算法零基础100讲》(第11讲) 因子数https://blog.csdn.net/WhereIsHeroFrom/article/details/120875407
https://blog.csdn.net/WhereIsHeroFrom/article/details/120875407
一、主要知识点
因数的个数判别
其中国ei为n的包含的每个质因子的个数。
对于
有 
二、课后习题详解
The number of divisors
The number of divisors(约数) about Humble Numbershttp://acm.hdu.edu.cn/showproblem.php?pid=1492
http://acm.hdu.edu.cn/showproblem.php?pid=1492
思路
题目说的意思是给你一个树只包含2、3、5、7因子，你需要返回它包含的所有因子数量。
思路，求出它包含的每个质因子数量做乘积就好了
#include<cstdio> int main(){ long long n; int yueshu[] = {2,3,5,7}; //所有的约数 while(scanf("%lld",&n) != EOF && n != 0){ //输入的判定 long long ans = 1; //结果 for(int i = 0;i < 4;++i){ int count = 0; for(;n % yueshu[i] == 0;n /= yueshu[i]) count ++; //判断约数的个数 ans *= count + 1; //公式 } printf("%lld\n",ans); } return 0; }
结果分析
还行吧。。。
本原串
本原串http://acm.hdu.edu.cn/showproblem.php?pid=2197
http://acm.hdu.edu.cn/showproblem.php?pid=2197
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。
思路
其实大的n的本源串和小的本源串是有关系的，我们来观察一下。
F(1) = 2;
F(2) = 2^2 - F(1) = 2;
F(3) = 2^3 - F(1) = 6;
F(4) = 2^4 - F(2) - F(1) = 12;
其实很容易理解，如果一个数字含有这个因子，那么就将那个因子对应的本源串减去。因为有这个因子就可以由这个因子产生的本源串产生。比如 00 01 10 11中 00 和11 就是1对应的0 和1 产生的。
有了这样的思路，程序并不难写出，值得注意的是可以将计算过的结果进行记录，方便下次使用。
#include<cstdio> int F[100000005] = {0}; int pow_mod(long long a,long long n,int Mod){//快速二分幂的非递归实现 long long ans=1; while(n){ if(n & 1) ans = ans * a % Mod; a = a * a % Mod; n>>=1; } return ans % Mod; } int get_num(int n){ if(F[n]) return F[n]; int num = pow_mod(2,n,2008) - F[1]; int i; for(i = 2;i*i <n;++i){ if(n % i == 0){ num = (num - get_num(i))%2008; num = (num - get_num(n/i))%2008; } } if(i*i == n) num = (num - get_num(i))%2008; F[n] = (num +2008)%2008; return F[n]; } int main(){ F[1] = 2; int n; while(scanf("%d",&n) != EOF){ if(n < 2) printf("%d\n",F[n]); else{ if(!F[n]) F[n] = get_num(n); printf("%d\n",F[n]); } } return 0; }
结果分析
感觉还能优化，但是肝不动了。。。
课后总结
今天要好好做作业。。。时间都去哪了。。。不够用啊-.-
