Haut OJ 2021 freshmen week II reflection summary

problem E: Prime judgement of Niuniu

Problem description ：

Niuniu recently learned to judge primes , But Niuniu's friends don't believe that they want to test him , I asked him ： Here are two numbers for you a,b, Judge a×b Is it a prime .
Prime numbers are greater than 1 In the positive integer of , A number with only two factors .
（PS:1e11=10 Of 11 Power ）

Input ：

Enter an integer in the first line T, representative T Group data . Next T That's ok (1<=T<=10), Two integers per line a,b(1<=a,b<=1e11).

Output ：

For each line of input, if ,a×b If it is a prime number, output a line YES, Otherwise, output a line NO.

The sample input ：

3
2 3
1 7
1 4

Sample output ：

NO
YES
NO

---

Cause analysis ：

Data is too natural to multiply , Also have to long long, a*b As a prime number , Prime numbers are only 1 Multiplied by itself , Therefore, it is only necessary to judge whether there is one of the two numbers 1, And whether the other is a prime number .

---

Solution ：

#include<bits/stdc++.h>
using namespace std;
int prime (long long n)
{
    long long i,k=sqrt(n);
    if(n==1)
        return 0;
    if(n==2)
        return 1;

    for(i=2;i<=k;i++)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    long long a,b,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        if(a==1&&prime(b)||b==1&&prime(a))
        {
            cout<<"YES"<<endl;
        }
        else
            cout<<"NO"<<endl;
    }



}

problem G: The number of cycles of Niuniu

Problem description ：

Niuniu knows , In programming , Time complexity needs to be considered , Especially for the part of the loop . for example , If there is... In the code

for(i=1;i<=n;i++) OP ;

So I did n Time OP operation , If there is... In the code

for(i=1;i<=n; i++)
  for(j=i+1;j<=n; j++) OP;

So I did n*(n-1)/2 Time OP operation .
Niuniu wrote the following code ：

for(i=1;i<=n; i++)
  for(j=i+1;j<=n; j++)
     for(k=j+1;k<=n;k++)OP;

Now we know n, Niuniu wants to know how many times it has been done OP operation .

Input ：

First line input 1 It's an integer T(1<=T<=100), On behalf of T Group data
Next T That's ok , One positive integer per line n(1<=n<=1000)

Output ：

For each set of data , Output in one line OP The number of operations .

The sample input ：

4
3
4
5
6

Sample output ：

1
4
10
20

---

Cause analysis ：

Three for loop , In fact, it is equivalent to 1~n Choose three numbers , That is, arrangement and combination , But pay attention to ：

take 5 give an example , take 1 2 3 Only 1 2  3 No, 2 3 1, That is, the ball can only be taken from small to large , namely C（3,5） perhaps

A(3,n)/A(3,3) ,  C（3,5） It can be understood as the default of three numbers from small to large .

---

Solution ：

1. Yang Hui trigonometrically asks C

#include<bits/stdc++.h>
using namespace std;

const int N = 2000;


int c[N+1][N+1];

void initc()
{
    c[0][0] = 1;
    for(int i=1; i<=N; i++) {
        c[i][0] = 1;
        for(int j=1; j<=N; j++)
            c[i][j] = (c[i-1][j-1] + c[i-1][j]);
    }
}


int main()
{
    int t, n;

    initc();

    cin >> t;
    while(t--) {
        cin  >> n;

        cout << c[n][3] << endl;
    }
    return 0;
}

2. Simplify combinatorial operations .

There is a number for 1~5 Of 5 A little ball , take 3 A little ball , Then there are A(3,5)=60 In this case , But each group appeared 6 Time , Such as 1,2,3 This combination has A(3,3)=6 In this case , But only (1,2,3) This kind meets the requirements , So we can get the formula A(3,n)/A(3,3).

#include<stdio.h>
int main()
{
    int n,T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int cnt=0;
        cnt=n*(n-1)*(n-2)/6;
        printf("%d\n",cnt);
    }
     
}

  Sudoku of Niuniu

Problem description ：

Niuniu met a 9×9 The Sudoku of , You can help Niuniu judge whether Sudoku is effective . Just follow the rules , Verify that the numbers you have filled are valid .
1. Numbers 1-9 Only once in a row .
2. Numbers 1-9 It can only appear once in each column .
3. Numbers 1-9  Separated by thick solid lines in each  3x3  Only once in the palace .（ Pictured ）

---

Cause analysis ：

The idea is simple , There are several points to pay attention to .

1. In the array i,j Swap is from row judgment to column judgment .

2. Be careful ans[i][j]==0 When directly continue;

3. When judging the Jiugongge , You can put 9*9 Approximate as 3*3, That is the two one. for from 0~3, Then there is another one in each big room 3*3 Small palace lattice of , namely Add two more cycles , 

for(ii=3*i;ii<3*i+3;ii++)  
 for(jj=3*j;jj<3*j+j;jj++)

---

Solution ：

、

#include<bits/stdc++.h>
using namespace std;


int main()
{
  int i,j,ans[10][10],ii,jj;
  for(i=0;i<9;i++)
  {
      for(j=0;j<9;j++)
        cin>>ans[i][j];
  }
  for(i=0;i<9;i++)
  {
      int a[10]={0};
      for(j=0;j<9;j++)
      {
          if(ans[i][j]==0)
            continue;

          if(a[ans[i][j]]==0)
          {
             a[ans[i][j]]=1;
          }
          else if(a[ans[i][j]]>0)
          {
              printf("no\n");
              return 0;
          }

      }
  }

    for(i=0;i<9;i++)
  {
      int a[10]={0};
      for(j=0;j<9;j++)
      {
          if(ans[j][i]==0)
            continue;


          if(a[ans[j][i]]==0)
          {
              a[ans[j][i]]=1;
          }
          else if(a[ans[j][i]]>0)
          {
              printf("no\n");
              return 0;
          }

      }
  }
  for(i=0;i<3;i++)
  {
      for(j=0;j<3;j++)
      {
          int a[10]={0};
          for(ii=3*i;ii<3*i+3;ii++)
          {
              for(jj=3*j;jj<3*j+j;jj++)
              {
                  if(ans[ii][jj]==0)
                   continue;

                  if(a[ans[ii][jj]]==0)
                    a[ans[ii][jj]]=1;
                  else if(a[ans[ii][jj]]>0)
                  {
                      printf("no\n");
                      return 0;
                  }
              }
          }
      }
  }
  printf("yes\n");
  return 0;

}

reflection ：

1. Thinking is not flexible enough , Constantly complicate the problem .

2. Too anxious AC 了 , I didn't notice the details , The first question is wa, See the question clearly .

3. Continue to strengthen the practice of strings