Submission #9266

#	Time	Username	Problem	Language	Result	Execution time	Memory
9266		pichulia	Phibonacci (kriii2_P)	C++98	1 / 4	1000 ms	1088 KiB

P

#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];
	long long int r[5];
	z[0] = 1;
	z[1] = 0;
	x[0] = sq;
	x[1] = sp;
	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)
	{
		while(1)
		printf("0 %lld\n",z[0]);
		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);

}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 3