hdu 3221 Brute-force Algorithm (矩阵快速幂+指数循环节)

题目链接

 

题意:给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2]

思路:一眼题,和hdu4549很类似hdu4549解题报告

不同的是这道题中p不一定是质数(其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数,又用费马小定理化简了一下,这道理%phi(p)即可)

还有这道题让我知道了

首先我们知道指数循环节公式,也就是所谓的降幂公式为:a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c),(ps:后面的限制条件,在x<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

括号里的话是错误的。只有当x<phi(c)的时候,这个公式才成立。

这道题就是反例,不加判断会wa。

 

 

 

hdu 2837 Calculation (指数循环节+欧拉函数)

题目链接

题意:

Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).
思路:指数循环节。
trick点在于0^0=1这点。
比较容易想到的一层是ksm的时候特判。
比较不容易想到的一层是,0作为底数的时候,可能出现0^a在用降幂公式加速后,出现0^0。
举个例子:
680 80
phi(80)=32,恰好是8^6的因子
而0^(8^6)答案应该为0,用降幂公式加速后变成了0^0,答案变成了1,结果错误
究其原因,是因为这道题中底数可能有0以及0^0是题目中定义的运算。
解决办法是ksm的结果判断一下,如果是0就加mod。

 

hdu 4335 What is N? (指数循环节+欧拉函数)

题目链接

题意:给出b,p,m(( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 – 1 )),问满足图中条件的n有多少个。

思路:这题由于对p没有限制,所以细节多一些,需要讨论。

首先我们知道指数循环节公式,也就是所谓的降幂公式为:a^x = a^(x mod phi(c)+phi(c)) (mod c) x>=phi(c),(ps:后面的限制条件,在x<phi(c)的时候,该式子依然正确,只不过增加了运算复杂度。。。? 存疑)

然后我们只需要对n分两种情况讨论。

第一种是n<t ,第二种是n>=t  (t = min{x| x! % phi(P)==0})

由于t不会很大。。前一种直接暴力。。。

后一种用降幂公式搞之。。。

 

 

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接

题意:求一个楼梯数%m的大小。

思路:指数循环节。

需要注意的是,模数只有最外层是m,每往里一层,模数都变成m=phi(m)

所以可以写个dfs或者先预处理出每一层m存一下。

记得考虑n=1的特殊情况。

 

 

hdu 4704 Sum (隔板法,指数循环节,费马小定理)

题目链接

题意:定义s(k)为将n分成k个正整数的划分数,给出n,问s(1) + s(2) + … + s(n-1) + s(n)是多少,结果%1E9+7,其中n<=10^100000。

思路:首先化简要求的式子。

根据隔板法_维基百科

现在有10个球,要放进3个盒子里

●●●●●●●●●●

隔2个板子,把10个球被隔开成3个部分

●|●|●●●●●●●●、●|●●|●●●●●●●、●|●●●|●●●●●●、●|●●●●|●●●●●、●|●●●●●|●●●●、●|●●●●●●|●●●、……

如此类推,10个球放进3个盒子的方法总数为{{\binom {10-1}{3-1}}={\binom {9}{2}}=36

n个球放进k个盒子的方法总数为{{\binom {n-1}{k-1}}

问题等价于求{x_{1}+x_{2}+...+x_{k}=n的可行解数,其中x_{1},x_{2},...,x_{k}正整数

 

于是问题转化成:

n个木棍,n-1个缝,

分成1份则是C(n-1,0);

分成2份则是C(n-1,1);

分成3份则是C(n-1,2);

分成n份则是C(n-1,n-1);

ans = sum( C(n-1,i) ) (0<=i<=n-1)

=2^(n-1);

 

这是我能理解的得到2^(n-1)的方式。。。

看到有好多人说这个结论是显然的。。。求指教(说这是个结论记住就好的就算了23333)

接下来,就是求A=2^(n-1)%1E9+7的问题了。。。

根据指数循环节公式A=2^((n-1)%(mod-1))*2^(mod-1)%mod (其中mod=1E9+7)

由于gcd(2,1E9+7)=1,根据费马小定理2^(mod-1)%mod=1,因此A=2^((n-1)%(mod-1))

然后快速幂搞之。

 

 

 

hdu 4549 M斐波那契数列 (矩阵快速幂+费马小定理+指数循环节)

题意:M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n,你能求出F[n]的值吗?

思路:观察发现。。。F[n] = a^(fib(n-1)) * b ^ (fib(n))

此处要用到指数循环节的知识:

111qqz_指数循环节学习笔记

a^n ≡ a^(n % Phi(M) + Phi(M)) (mod M) (n >= Phi(M))

然后 因为1000000007是质数,对于任意的x,有gcd(x,1000000007) = 1,所以可以结合费马小定理化简上式:

a^n ≡ a^(n%(m-1)) * a^(m-1)≡ a^(n%(m-1)) (mod m)

记得特判一下n为0和1的情况。

xiaodingli