fibonacci 수열의 성질(ZOJ3707)
제목:
Define S[n] as the number of subsets of {1, 2, ...,n} that contain no consecutive integers. For eachS[n], if for alli (1 ≤i < n) gcd(S[i],
S[n]) is 1, we call thatS[n] as aPrime S. Additionally,S[1] is also a Prime S. For theKth minimumPrime S, we'd like to find the
minimum S[n] which is multiple ofX and not less than theKth minimumPrime S. Please tell us the corresponding (S[n] ÷X) modM.
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]
또 하나의 결론은
계산(a/b)%c 그중 b는 a를 제거할 수 있다
만약 b와 c가 상호작용을 한다면, (a/b)%c=a*b^(phi(c)-1)%c
만약 b와 c가 서로 어울리지 않는다면, (a/b)%c=(a%bc)/b
b와 c의 상호작용과 상호작용은 모두 (a/b)%c=(a%bc)/b가 성립된다
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long LL;
const LL N=16000000;
LL p[N];
bool prime[N];
LL k=1;
void isprime()
{
LL i,j;
p[0]=1;
memset(prime,true,sizeof(prime));
for(i=2;i<N;i++)
{
if(prime[i])
{
p[k++]=i;
for(j=i+i;j<N;j+=i)
{
prime[j]=false;
}
}
}
p[1]=3;p[2]=4;
}
typedef struct
{
LL m[2][2];
}Matrix;
Matrix per={1,0,0,1};
Matrix a={1,1,1,0};
Matrix multi(Matrix a,Matrix b,LL MOD)
{
Matrix c;
LL i,j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c.m[i][j]=0;
for(k=0;k<2;k++)
{
c.m[i][j]+=a.m[i][k]*b.m[k][j];
c.m[i][j]%=MOD;
}
}
}
return c;
}
Matrix matrix_mod(LL k,LL MOD)
{
Matrix p=a,ans=per;
while(k)
{
if(k&1)
{
ans=multi(ans,p,MOD);
k--;
}
k>>=1;
p=multi(p,p,MOD);
}
return ans;
}
int main()
{
LL K,X,M,t,i,ret,r;
isprime();
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld",&K,&X,&M);
Matrix ans;
for(i=p[K];;i++)
{
ans=matrix_mod(i-1,X);
if((ans.m[0][0]%X==0))
{
r=i;
break;
}
}
ans=matrix_mod(i-1,M*X);
ret=ans.m[0][0]/X;
printf("%lld
",ret);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.