Number Theory – VOID001's WOWO

[转]Fibonacci 数列的基本性质

十二月 20, 2014 VOID001 Comments 0 Comment

fibonacci数列的性质：

1.gcd(fib(n),fib(m))=fib(gcd(n,m))

证明：可以通过反证法先证fibonacci数列的任意相邻两项一定互素，然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，递归可

求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最后k=l，不然继续递归。K是通过展转相减法求出，易证k=gcd(n,m)，所以gcd(fib(n),fib(m))

=fib(gcd(n,m))。

2.如果fib(k)能被x整除，则fib(k*i)都可以被x整除。

3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1

4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)

5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1

6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)

7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1

8.f(n+m)=f(n+1)·f(m)+f(n)*f(m-1)

9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)

10.f(2n-1)=[f(n)]^2-[f(n-2)]^2

11.3f(n)=f(n+2)+f(n-2)

12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

十二月 20, 2014 VOID001 Comments 0 Comment

Calculate Prime S

Time Limit: 2000MS

Memory Limit: 262144KB

64bit IO Format: %lld & %llu

Description

Define S[n] as the number of subsets of {1, 2, …, n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the K^th minimum Prime S, we’d like to find the minimum S[n]which is multiple of X and not less than the K^th minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M.

Input

There are multiple test cases. The first line of input is an integer T indicating the number of test cases.

For each test case, there are 3 integers K (1 ≤ K ≤ 10⁶), X (3 ≤ X ≤ 100) and M (10 ≤ M ≤ 10⁶), which are defined in above description.

Output

For each test case, please output the corresponding (S[n] ÷ X) mod M.

Sample Input

1
1 3 10

1 3 10

culate Prime S
Sample Output

1

解决这个问题需要的知识储备为：

Fibonacci数列的性质
矩阵快速幂计算Fibonacci
取模运算的性质 (a/b)%c=(a%b*c)/b

在这里有Fibonacci数列的基本性质，快速幂的知识在这里有，矩阵快速幂的代码在下面，理解了快速幂之后很好理解。

本题首先要读清题目，本题涉及的元素较多，滤清思路之后本题要求的是不小于第 K 个 Prime S 的能被X整除的S 序列里的数字，而经过我们小数据打表发现 S序列为Fibonacci数列从第三项开始也就是 2 3 5 8 13 … 而 Prime S 为 Fibonacci数列里的素数，由Fibonacci的性质知，Fibonacci中第n项为Fibonacci素数的条件是 n为质数当 n>=5时成立，所以我们可以通过这个性质结合素数表来获得第 K个Fibonacci素数在Fibonacci数列里的下标在代码的注释里有具体例子。然后我们就可以往后枚举这个下标用矩阵快速幂的方法来求第n个Fibonacci数，然后找到能被X整除的，并进行 S/X %C = （S%XC）/X 的运算把结果输出即可 由于我的素数生成函数(筛法)把count的初值设置错误导致开始一直在错，另外需要注意 p[1] 和 p[2]的值要特殊处理至于为何前面已经讲过了

下面是代码

/*************************************************************************
    > File Name: C.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: 2014年12月20日 星期六 13时12分59秒
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;

typedef long long LL;

const LL maxn=16000000;
LL p[maxn];
bool prime[maxn];

void genPrime()
{
	prime[0]=0;
	prime[2]=1;
	memset(prime,true,sizeof(prime));
	//int count=0;						//Here is a big mistake!
	int count=1;						
	for(int i=2;i<maxn;i++)
	{
		if(prime[i])
		{
			p[count++]=i;	
			for(int j=i+i;j<maxn;j+=i)
			{
				prime[j]=false;
			}
		}
	}

	p[1]=3;
	p[2]=4;
	//p[k] Store the index of the k th Prime S in Fibonacci Series
	//Example:
	//p[1]=3 means the index of the first Prime S (which is 2) in Fibonacci Series is 3 
	// VERY IMPORTANT!!!
	return ;
}

typedef struct 
{
	LL m[2][2];
}Matrix;

Matrix multi(Matrix a,Matrix b,LL MOD)
{
	Matrix c;
	LL i,j;
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<2;j++)
		{
			c.m[i][j]=0;
			for(int k=0;k<2;k++)
			{
				c.m[i][j]+=a.m[i][k]*b.m[k][j];
				c.m[i][j]%=MOD;						//Use MOD to make the number smaller
			}
		}
	}
	return c;
}

Matrix per={1,0,0,1};
Matrix samp={1,1,1,0};

Matrix matrixQuickPow(LL k,LL MOD)
{
	Matrix ans=per;
	Matrix p=samp;
	while(k)
	{
		if(k&1)
		{
			ans=multi(ans,p,MOD);
			k--;
		}
		p=multi(p,p,MOD);
		k>>=1;
	}
	return ans;
}

int main(void)
{
	LL X,M,K;
	genPrime();
	int T;
	scanf("%d",&T);
	LL mem;
	while(T--)
	{
		scanf("%lld%lld%lld",&K,&X,&M);
		Matrix ans;
		for(LL i=p[K];;i++)
		{
			ans=matrixQuickPow(i-1,X);
			if(ans.m[0][0]%X==0)
			{
				mem=i;
				break;
			}
		}
		ans=matrixQuickPow(mem-1,X*M);
		LL res=ans.m[0][0]/X;
		printf("%lldn",res);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

/*************************************************************************

> File Name: C.cpp

> Author: VOID_133

> ###################

> Mail: ###################

> Created Time: 2014年12月20日星期六 13时12分59秒

************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

using namespace std;

typedef long long LL;

const LL maxn=16000000;

LL p[maxn];

bool prime[maxn];

void genPrime()

{

prime[0]=0;

prime[2]=1;

memset(prime,true,sizeof(prime));

//int count=0; //Here is a big mistake!

int count=1;

for(int i=2;i<maxn;i++)

{

if(prime[i])

{

p[count++]=i;

for(int j=i+i;j<maxn;j+=i)

{

prime[j]=false;

}

p[1]=3;

p[2]=4;

//p[k] Store the index of the k th Prime S in Fibonacci Series

//Example:

//p[1]=3 means the index of the first Prime S (which is 2) in Fibonacci Series is 3

// VERY IMPORTANT!!!

return ;

}

typedef struct

{

LL m[2][2];

}Matrix;

Matrix multi(Matrix a,Matrix b,LL MOD)

{

Matrix c;

LL i,j;

for(int i=0;i<2;i++)

{

for(int j=0;j<2;j++)

{

c.m[i][j]=0;

for(int k=0;k<2;k++)

{

c.m[i][j]+=a.m[i][k]*b.m[k][j];

c.m[i][j]%=MOD; //Use MOD to make the number smaller

}

return c;

}

Matrix per={1,0,0,1};

Matrix samp={1,1,1,0};

Matrix matrixQuickPow(LL k,LL MOD)

{

Matrix ans=per;

Matrix p=samp;

while(k)

{

if(k&1)

{

ans=multi(ans,p,MOD);

k--;

}

p=multi(p,p,MOD);

k>>=1;

}

return ans;

}

int main(void)

{

LL X,M,K;

genPrime();

int T;

scanf("%d",&T);

LL mem;

while(T--)

{

scanf("%lld%lld%lld",&K,&X,&M);

Matrix ans;

for(LL i=p[K];;i++)

{

ans=matrixQuickPow(i-1,X);

if(ans.m[0][0]%X==0)

{

mem=i;

break;

}

ans=matrixQuickPow(mem-1,X*M);

LL res=ans.m[0][0]/X;

printf("%lldn",res);

}

return 0;

}

VOID001's WOWO

✵Merry Christmas✵ Aim at being kernel hacker, now a newbie

Browsed by
分类：Number Theory

[转]Fibonacci 数列的基本性质

十二月 20, 2014 VOID001 Comments 0 Comment

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

十二月 20, 2014 VOID001 Comments 0 Comment