Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
输入矩阵的行数，再依次输入矩阵的每行元素，判断该矩阵是否为对称矩阵，若矩阵对称输出“yes"，不对称输出”no“。
Input
输入有多组，每一组第一行输入一个正整数N（N<=20），表示矩阵的行数（若N=0，表示输入结束）。

下面依次输入N行数据。
Output
若矩阵对称输出“yes"，不对称输出”no”。
Sample Input
3

6 3 12

3 18 8

12 8 7

3

6 9 12

3 5 8

12 6 3

0
Sample Output
yes

no
Hint

Source
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int n;
    int i,j;
    int a[21][21];
    while(~scanf("%d",&n)&&n)    //多组输入若为EOF或者n==0都将结束输入
    {
        int flag=1;   //定义标记变量；
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);   //输入数据；
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<i;j++)
            {
                if(a[i][j]!=a[j][i])    //若出现一组不对称的数据则标记变量flag=0且结束循环；
                {
                    flag=0;
                    break;

                }
            }
            if(j<i)
                break;   //若上一个for循环为非正常结束，则外层循环也结束
        }
        if(flag)
            printf("yes\n");
        else
            printf("no\n");
    }

    return 0;
}


运行结果：
3
6 3 12
3 18 8
12 8 7
yes
3
6 9 12
3 5 8
12 6 3
no
0

Process returned 0 (0x0)   execution time : 27.657 s
Press any key to continue.

问题

顺时针循环打印一个矩阵元素。

https://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/

难点：如何控制下一步该往哪里走？

思路

想法一：如何控制下一步？下一步是由当前方向决定的。所以最直观的想法就是维护一个方向变量，然后建立一个偏移量的二维数组，第一维传入的方向，大小为4，第二维是x和y方向的前进量，大小为2。然后我们就根据方向来获取下一步移动的偏移量，如果碰壁，就修改方向，方向的修改是一个从大小为4的循环数组中轮流取值的过程。这个思路是可行的。当然还需要判定停止条件，可以用一个辅助数组记录哪些遍历过，如果遍历到一个已经遍历过的元素，就跳出，这是一种思路。

想法二：

想法一是可行的，但是其实可以省去方向变量和标记的过程，思考的模式变一下。

每一次x和y变化的坐标只有一个，所以我们只需要一个遍历指针（其实是变量）；

整个过程可以看成是多轮遍历，每一轮包括四个方向，绕一圈；

也就是抽象为：

while(){

    for()

    for()

    for()

    for()

}

每一个内部的for，都会限定遍历的范围，遍历完就更新边界值。还要想好跳出的条件，就是遍历完一行或者一列，导致下一次没有空余的行或者列遍历了，也就是for之前判定一下行号或者列号的最大值是否小于最小值，如果是就break。那是不是每一个for循环都要判定？都判定肯定没问题，如果想要精简代码，只需要判定一个列的遍历和一个行的遍历即可。因为总会走到这个判定里。并且每一个for循环内部也不会受影响，因为for内部有条件限制。

代码

    public static void rotate(int[][] array) {
          //遍历指针
          int i;
          //边界
          int l = 0, k = 0, m = array.length - 1, n = array[0].length - 1;
          //主循环
          while (true) {
              //遍历上面的行
              for (i = k; i <= n; i++) {
                  System.out.println(array[l][i]);
              }
              //遍历完修改行的最小边界
              l ++;
              //遍历右侧的列
              for (i = l; i <= m; i++){
                  System.out.println(array[i][n]);
              }
              //遍历完修改列的右边界
              n --;
              
              //检测行是否遍历完了，如果碰上了，说明该退出
              if (l > m) {
                  break;
              }
              //遍历下面的行
              for (i = n; i >= k; i--) {
                System.out.println(array[m][i]);
              }
              //遍历完修改行的最大边界
              m--;
              //检测列是否遍历完了，如果碰上了，说明该退出
              if (k > n) {
                  break;
              }
              //遍历左侧的列
              for (i = m; i >= l; i--) {
                  System.out.println(array[i][k]);
              }
              //遍历完修改列的左边界
              k++;
          }
    }

 

解题思路：

先说明一下结论在下都不会证明，囧……。

对于一个正整数n，我们求Fib数模n的循环节的长度的方法如下： 
(1)将n分解质因数，即n=pk11pk22……pkmm
(2)分别计算Fib数模pkii的循环节的长度，假设是x1,x2,……xm
(3)则Fib数模n的循环节的长度为ans=lcm(x1,x2,……xm)

从上面三个步骤看来，貌似最困难的是第二步，那么我们如何求Fib数模pm的循环节长度呢？

这里有一个优美的定理：

Fib数模pm的循环节长度等于G(p)∗pm−1，其中G(p)表示Fib数模p的循环节长度

那么现在的关键在于如何求G(p)。

当p≤5，直接手算。

当p>5，又有结论如下：

当5是模p的二次剩余，即方程x2≡5(modp)有解，那么循环节长度是(p−1)的约数，否则是2(p+1)的约数

之所以与5有关是因为斐波那契通项公式里唯一的无理数是5√，x相当于起到了5√的作用。

接下来直接dfs枚举约数，加上矩阵快速幂判定即可，即满足f[ans+1]=f[ans+2]=1。注意矩阵乘法要手写卡常数。

这里提一下如何判定a是否是模质数p的二次剩余，即方程x2≡a(modp)是否有解的判定方法。 

该方法叫做欧拉判定准则：

当ap−12≡1(modp)，则a是模p的二次剩余，反之，即ap−12≡−1(modp)则不是

这个可以用费马小定理证明。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#define ll long long
using namespace std;

int getint()
{
    int i=0,f=1;char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if(c=='-')c=getchar(),f=-1;
    for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
    return i*f;
}

inline void W(long long x)
{
    x<0?putchar('-'),x=-x:0;
    static int buf[25];
    int tot=0;
    do{
        buf[tot++]=x%10,x/=10;
    }while(x);
    while(tot)putchar(buf[--tot]+'0');
}

const int N=100005;
const ll INF=1e18;
struct node
{
    int num,cnt;
    ll len;
}yz[50];
struct matrix
{
    int a[3][3];
    inline matrix I()
    {
        matrix res;
        res.a[1][1]=res.a[2][2]=1;
        res.a[1][2]=res.a[2][1]=0;
        return res;
    }
    inline friend matrix mul(const matrix &A,const matrix &B,const int &p)
    {
        matrix res;
        memset(res.a,0,sizeof(res.a));
        res.a[1][1]=(1ll*A.a[1][1]*B.a[1][1]+1ll*A.a[1][2]*B.a[2][1])%p;
        res.a[1][2]=(1ll*A.a[1][1]*B.a[1][2]+1ll*A.a[1][2]*B.a[2][2])%p;
        res.a[2][1]=(1ll*A.a[2][1]*B.a[1][1]+1ll*A.a[2][2]*B.a[2][1])%p;
        res.a[2][2]=(1ll*A.a[2][1]*B.a[1][2]+1ll*A.a[2][2]*B.a[2][2])%p;
        return res;
    }
    inline matrix Pow(int y,const int &p)
    {
        matrix res=I(),x=*this;
        for(;y;y>>=1,x=mul(x,x,p))
            if(y&1)res=mul(res,x,p);
        return res;
    }   
};
int T,n,tot;
ll t;
int pn,pri[N];
int len[N],tmp[N];
bool notp[N];

inline int ksm(int x,int y,int p)
{
    int res=1;
    for(;y;y>>=1,x=1ll*x*x%p)
        if(y&1)res=1ll*res*x%p;
    return res;
}

inline matrix Fib(int x,const int &p)
{
    matrix res,A;
    res.a[1][1]=res.a[2][1]=res.a[2][2]=0;
    res.a[1][2]=1;
    A.a[1][1]=0;
    A.a[1][2]=A.a[2][1]=A.a[2][2]=1;
    res=mul(res,A.Pow(x-1,p),p);
    return res;
}

inline void div(ll x)
{
    tot=0;
    for(int i=1;1ll*pri[i]*pri[i]<=x&&i<=pn;i++)
        if(x%pri[i]==0)
        {
            yz[++tot].num=pri[i],yz[tot].cnt=0,yz[tot].len=1;
            while(x%pri[i]==0)
            {
                x/=pri[i];
                yz[tot].cnt++;
            }
        }
    if(x!=1)yz[++tot].num=x,yz[tot].cnt=1,yz[tot].len=1;
}

void dfs(int x,ll num,int p)
{
    if(x==tot+1)
    {
        matrix A=Fib(num+2,p);
        if(A.a[1][1]==1&&A.a[1][2]==1)
            t=min(num,t);
        return;
    }
    dfs(x+1,num,p);
    ll d=1;
    for(int i=1;i<=yz[x].cnt;i++)
    {
        d*=yz[x].num;
        dfs(x+1,1ll*num*d,p);
    }
}

inline ll find(int p)
{
    if(p==2)return 3;
    if(p==3)return 8;
    if(p==5)return 20;
    t=INF; 
    if(ksm(5,(p-1)/2,p)==1)div(p-1);
    else div(2ll*(p+1));
    dfs(1,1,p);
    return t;
}

inline void sieve()
{
    int M=sqrt(1e9)+1;
    for(int i=2;i<=M;i++)
    {
        if(!notp[i])pri[++pn]=i,len[i]=find(i);
        for(int j=1;j<=pn;j++)
        {
            int k=i*pri[j];
            if(k>M)break;
            notp[k]=true;
            if(!i%pri[j])break;
        }
    }
}

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

inline void solve(int x)
{
    div(x);
    for(int i=1;i<=tot;i++)
    {
        for(int j=1;j<yz[i].cnt;j++)
            yz[i].len*=yz[i].num;
        if(1ll*yz[i].num*yz[i].num<=x)
            yz[i].len*=len[yz[i].num];
    }
    tmp[0]=tot;
    for(int i=1;i<=tot;i++)tmp[i]=yz[i].len;
    if(1ll*yz[tot].num*yz[tot].num>x)tmp[tmp[0]]=find(yz[tot].num);
    ll ans=1;
    for(int i=1;i<=tmp[0];i++)
        ans=1ll*ans*tmp[i]/gcd(ans,tmp[i]);
    W(ans),putchar('\n');
}

int main()
{
    //freopen("lx.in","r",stdin);
    //freopen("lx.out","w",stdout);
    sieve();
    T=getint();
    while(T--)
    {
        n=getint();
        solve(n);
    }
    return 0;
}

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
这题我想了很久都越想越复杂，写了个循环边缘判定把自己绕晕了，这题和leetcode54题一样，牛客网标答区有个说是转自leetcode解答的方法非常妙，比我之前存的答案更加易写易懂。简单来说，就是不断地收缩矩阵的边界

定义四个变量代表范围，up、down、left、right，判断是否和边界交错，懂了以后马上可以自己写。
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> ans = new ArrayList<>();
        int up = 0;
        int down = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while(true){
            for(int i = left; i <= right; i++){
                ans.add(matrix[up][i]);
            }
            up++;
            if(up > down) break;
            for(int i = up; i <= down; i++){
                ans.add(matrix[i][right]);
            }
            right--;
            if(left > right) break;
            for(int i = right; i >= left; i--){
                ans.add(matrix[down][i]);
            }
            down--;
            if(up > down) break;
            for(int i = down; i >= up; i--){
                ans.add(matrix[i][left]);
            }
            left++;
            if(left > right) break;
        }
        return ans;
    }
}

也附上之前存的两种解法
public List < Integer > spiralOrder(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0)
            return ans;
        int r1 = 0, r2 = matrix.length - 1;
        int c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int c = c1; c <= c2; c++) ans.add(matrix[r1][c]);
            for (int r = r1 + 1; r <= r2; r++) ans.add(matrix[r][c2]);
            if (r1 < r2 && c1 < c2) {
                for (int c = c2 - 1; c > c1; c--) ans.add(matrix[r2][c]);
                for (int r = r2; r > r1; r--) ans.add(matrix[r][c1]);
            }
            r1++;
            r2--;
            c1++;
            c2--;
        }
        return ans;
    }


public List<Integer> spiralOrder(int[][] matrix) {
        List ans = new ArrayList();
        if (matrix.length == 0) return ans;
        int R = matrix.length, C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < R * C; i++) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int cr = r + dr[di];
            int cc = c + dc[di];
            if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]){
                r = cr;
                c = cc;
            } else {
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;
    }