2015年4月17日 星期五

[HOJ 401] 完美小矩陣

作法:

原題等價於要找一個矩陣 A ,使得 A*A = k * I ,對兩邊取 det 可得 det(A)^2 = k^n ,所以 k^n 是完全平方數,所以可以得到:當 n 是奇數且 k 不是完全平方數的時候原題無解。而當 k 是完全平方數的時候顯然有解,只要選 sqrt( k ) * I 就可以了,所以問題剩下 n 是偶數且 k 不是完全平方數的情形。當 n = 2 時,設 A = [ a b ] [ c d ] ,直接算出 A^2 然後令他等於 k * I ,就可以得到一個簡單的構造:a = 1 , b = 1 , c = k - 1 , d = -1 。再來我是想到 n = 4 的時候可以構造讓左下角的 2*2 和右上角的 2*2 全部都是 0 ,然後左上角和右下角的就分別放 2*2 的構造,然後我就以為這樣只有構出 2 ^ x ,結果過好久才發現其實偶數都構出來了,因為只要把 2*2 的構造填滿整個主對角線,其他都放 0 就可以了。

code :



#include<bits/stdc++.h>
using namespace std;
 
int ans[105][105] ;
main()
{
    int n,k ;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n%2)
        {
            if(k<0) { printf("11111\n") ; continue ; }
            int sq=sqrt(k+0.5) ;
            if(sq*sq!=k) { printf("11111\n") ; continue ; }
            printf("22222\n") ;
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
                printf("%d%c",i==j?sq:0,j==n?'\n':' ') ;
        }
        else
        {
            memset(ans,0,sizeof(ans)) ;
            printf("22222\n") ;
            for(int i=1;i<=n;i+=2)
                ans[i][i]=1 , ans[i][i+1]=1 ,
                ans[i+1][i]=k-1 , ans[i+1][i+1]=-1 ;
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
                printf("%d%c",ans[i][j],j==n?'\n':' ') ;
        }
    }
}
 

沒有留言:

張貼留言