网站制作 招聘/seo站内优化包括

因子数求法

求因子数也是一个经常能遇到的问题。我们可以来一起想想因子数应该怎么求。

暴力

这是最直接就能想到的了，n的因子数就是枚举一次1~n的所有整数，如果能被n整除，因子数加一.这样时间复杂度是O（n）的

优化

注意到如果i是n的因子，那么n/i也是n的一个因子。因此，我们不需要枚举1~n的整数而只需要枚举1~$\sqrt{n}$就可以了。这样时间复杂度是O($\sqrt{n}$)的。

公式计算

将一个整数n分解质因数以后能得到$n=n{1}^{p1}+n{2}^{p2}+n{3}^{p3}+...$然后我们来看他的因子长什么样。他的因子分解质因子得到的质因子一定包含在n中（他是由n分出来的嘛）所以我们就有因子数就是n中每一个质因子取x个乘起来得到的。nk一共可以取0-pk个。所以就有$sum=(1+p1)+(1+p2)+(1+p3)+...$直接计算，时间复杂度就变成O(1)了

HDU1492.The number of divisors about Humble Numbers

题目链接

题目描述
给你一个只包含质因子2357的数，求他的所有因子的个数

有了上面的理论基础，这道题直接就能写出来

#include<iostream>using namespace std;typedef long long LL;int main()
{LL n;while (scanf("%lld", &n) != EOF , n){LL a = 0, b = 0, c = 0, d = 0;while (n % 2 == 0) a++, n /= 2;while (n % 3 == 0) b++, n /= 3;while (n % 5 == 0) c++, n /= 5;while (n % 7 == 0) d++, n /= 7;a++, b++, c++, d++;cout << a * b * c * d << endl;}
}

HDU2197.本原串

题目链接

题目描述
由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。

先来思考一个问题，长度为n的只包含01的串有多少种。对于每一个位置，我们都有两种选择要么放0要么放1，所以总共一共有$2^n$个不同的串。然后再来想办法删去其中不符合条件的串。不符合条件的串可以分成x个相同的串，就说明子串的长度p一定是总长度n的一个因数。这样思路就出来了，我们可以用递归按照同样的方法把所有的数量都求出来
关于快速幂看这里

可以用一个数组把算过的值都存起来，如果算过就可以直接返回。这样会快很多，可以自己试试（我懒得写了）

#include<iostream>using namespace std;typedef long long LL;
const int MOD = 2008;LL qpow(LL a, LL b)
{LL res = 1;while (b){if (b & 1) res = res * a % MOD;a = a * a % MOD;b >>= 1;}return res % MOD;
}LL find(LL n)
{if (n == 1) return 2;LL res = qpow(2, n);for (LL i = 2; i <= n / i; i++){if (n % i == 0){res = (res - find(i) ) % MOD; if (n / i != i) res = (res - find(n / i) ) % MOD;}}return res - 2 + MOD;
}int main()
{LL n;while (scanf("%lld", &n) != EOF){LL res = find(n);cout << res % MOD << endl;}
}