Submission #9200

#TimeUsernameProblemLanguageResultExecution timeMemory
9200pichuliaPhibonacci (kriii2_P)C++98
1 / 4
0 ms1088 KiB
#include<stdio.h> #include<algorithm> using namespace std; #define M 1000000007LL long long int n, m; long long int fibo(long long int y) { long long int x[4]; long long int z[4]; long long int r[4]; z[0] = z[3] = 1; z[1] = z[2] = 0; x[0] = x[1] = x[2] = 1; x[3] = 0; if(y<0) return 1; while(y) { int i, j, k; if(y%2) { for(i=0;i<4;i++) r[i] = 0; for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) { r[i*2+j] = (r[i*2+j] + z[i*2+k]*x[k*2+j])%M; } for(i=0;i<4;i++) z[i] = r[i]; } for(i=0;i<4;i++) r[i] = 0; for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) { r[i*2+j] = (r[i*2+j] + x[i*2+k]*x[k*2+j])%M; } for(i=0;i<4;i++) x[i] = r[i]; y/=2; } return z[1]; } long long int gcd_ext(long long int a) { long long int x,y,q,s[100],t[100],i; s[0]=1;t[0]=0; s[1]=0;t[1]=1; x=M;y=a; for(i=2;y;i++) { q=x/y; s[i]=s[i-2]-q*s[i-1]; t[i]=t[i-2]-q*t[i-1]; y^=x^=y^=x%=y; } return (t[i-2]+M+M)%M; } void process(long long int y,long long int sp,long long int sq) { long long int x[2]; long long int z[2]; z[0] = 1; z[1] = 0; x[0] = sq; x[1] = sp; long long int r[5]; while(y) { int i, j; if(y%2) { r[2] = (z[1] * x[1])%M; r[1] = (z[0]*x[1] + x[0]*z[1])%M; r[0] = (z[0] * x[0])%M; r[1] = (r[1]+r[2])%M; r[0] = (r[0]+r[2])%M; z[0] = r[0]; z[1] = r[1]; } r[2] = (x[1] * x[1])%M; r[1] = (x[0]*x[1] + x[0]*x[1])%M; r[0] = (x[0] * x[0])%M; r[1] = (r[1]+r[2])%M; r[0] = (r[0]+r[2])%M; x[0] = r[0]; x[1] = r[1]; y/=2; } long long int p = fibo(m); long long int q = fibo(m-1); if(p == 0) { printf("-1\n"); return; } long long int gg = gcd_ext(p); long long int pp,qq; pp = 1; qq = (q*gg)%M; qq = (M-qq)%M; p = (z[1] * gg)%M; q = (z[0] + qq*z[1])%M; printf("%lld %lld\n",p,q); } int main() { scanf("%lld %lld",&n,&m); long long int p,q; p = fibo(n); q = fibo(n-1); process(m,p,q); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...