Submission #8845

#	Time	Username	Problem	Language	Result	Execution time	Memory
8845		gs13068	Quaternion inverse (kriii2_Q)	C++98	4 / 4	564 ms	1088 KiB

Q

#include<cstdio>

long long a[4][5];
long long t[4];

long long f(long long x,long long y,long long z)
{
	if(y==0)return 1;
    if(y&1)return f(x,y-1,z)*x%z;
    long long t=f(x,y>>1,z);
    return t*t%z;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int i,j,k,l,tt;
		for(i=0;i<4;i++)scanf("%lld",&t[i]);
        a[0][0]=t[0];
        a[0][1]=-t[1];
        a[0][2]=-t[2];
        a[0][3]=-t[3];
        a[0][4]=1;
        a[1][0]=t[1];
        a[1][1]=t[0];
        a[1][2]=-t[3];
        a[1][3]=t[2];
        a[1][4]=0;
        a[2][0]=t[2];
        a[2][1]=t[3];
        a[2][2]=t[0];
        a[2][3]=-t[1];
        a[2][4]=0;
        a[3][0]=t[3];
        a[3][1]=-t[2];
        a[3][2]=t[1];
        a[3][3]=t[0];
        a[3][4]=0;
        for(i=0;i<4;i++)
		{
			for(j=0;j<4;j++)
			{
				for(k=0;k<4;k++)if(a[j][k])break;
                if(k==i)break;
			}
			if(j==4)continue;
			for(k=0;k<4;k++)
			{
				if(j==k)continue;
                tt=a[k][i];
                for(l=0;l<5;l++)
				{
					a[k][l]*=a[j][i];
                    a[k][l]-=a[j][l]*tt;
                    a[k][l]%=n;
                    a[k][l]+=n;
                    a[k][l]%=n;
				}
			}
		}
		for(i=0;i<4;i++)
		{
			for(j=0;j<4;j++)if(a[i][j])break;
			if(j==4&&a[i][4])break;
		}
		if(i==4)
		{
			for(i=0;i<4;i++)t[i]=0;
            for(i=0;i<4;i++)for(j=0;j<4;j++)if(a[i][j])
			{
				t[j]=a[i][4]*f(a[i][j],n-2,n)%n;
				break;
			}
			for(i=0;i<4;i++)printf("%lld ",t[i]);
			puts("");
		}
		else puts("0 0 0 0");
	}
}

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