Submission #9339

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

P

#include<stdio.h>
#include<algorithm>
using namespace std;
#define M (1000000007LL)
long long int n, m;
struct A{
	long long int p,q;
	A(long long int x,long long int y){p=x; q=y;}
	A(){p=q=0;}
	A friend operator +(A p, A q)
	{
		long long int pp,qq;
		qq = (p.q + q.q)%M;
		pp = (p.q + q.q)/M;
		pp = (pp + p.p + q.p)%M;
		return A(pp,qq);
	}
	A friend operator *(A p, A q)
	{
		long long int pp,qq;
		qq = (p.q * q.q)%M;
		pp = (p.q * q.q)/M;
		pp = (pp + p.p * q.q + p.q*q.p)%M;
		return A(pp,qq);
	}
};
A fibo(long long int y)
{
	A x[4];
	A z[4];
	A r[4];
	z[0] = z[3] = A(0,1);
	z[1] = z[2] = A(0,0);
	x[0] = x[1] = x[2] = A(0,1);
	x[3] = A();
	if(y<0) return A(0,1);
	while(y)
	{
		int i, j, k;
		if(y%2)
		{
			for(i=0;i<4;i++)
				r[i] = A();
			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]);
				}
			for(i=0;i<4;i++)
				z[i] = r[i];
		}
		for(i=0;i<4;i++)
			r[i] = A();
		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]);
			}
		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,A sp,A sq)
{
	A x[2];
	A z[2];
	A r[5];
	z[0] = A(0,1);
	z[1] = A();
	x[0] = sq;
	x[1] = sp;
	while(y)
	{
		int i, j;
		if(y%2)
		{
			r[2] = (z[1] * x[1]);
			r[1] = (z[0]*x[1] + x[0]*z[1]);
			r[0] = (z[0] * x[0]);
			r[1] = (r[1]+r[2]);
			r[0] = (r[0]+r[2]);

			z[0] = r[0];
			z[1] = r[1];
		}
			r[2] = (x[1] * x[1]);
			r[1] = (x[0]*x[1] + x[0]*x[1]);
			r[0] = (x[0] * x[0]);
			r[1] = (r[1]+r[2]);
			r[0] = (r[0]+r[2]);

			x[0] = r[0];
			x[1] = r[1];

		y/=2;
	}
	A p = fibo(m);
	A q = fibo(m-1);
	if(p.q == 0 )
	{
		long long int gg = gcd_ext(p.p);
		long long int ppp = (gg*z[1].p)%M;
		long long int qqq = (ppp*q.q)%M;
		qqq = (M-qqq)%M;
		printf("%lld %lld\n",ppp, (qqq+z[0].q)%M);
		return;
	}
	long long int gg = gcd_ext(p.q);
	long long int pp,qq;
	pp = 1;
	qq = (q.q*gg)%M;
	qq = (M-qq)%M;
	long long ppp = (z[1].q * gg)%M;
	long long qqq = (z[0].q + qq*z[1].q)%M;
	printf("%lld %lld\n",ppp,qqq);
}
int main()
{
	scanf("%lld %lld",&n,&m);
	A p,q;
	p = fibo(n);
	q = fibo(n-1);
	process(m,p,q);

}

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