Article From:https://www.cnblogs.com/NSD-email0820/p/9530997.html

Question face

Consider a snooker table with only four pockets on each corner (shown below). We use the integer points on all the table boundaries as the hitting points (except for four pockets), and we can hit the ball at a 45-degree angle at each hitting point. You can hit the ball in two directions at every stroke.For example, as shown in the following figure, there are two ways to click from S.

Given the size of the table, your task is to figure out how many different hits there are to get the ball into the bag. The ball can be regarded as a particle without any resistance, and there is no energy loss when it bounces.

Input format
There is only one row, two integers m and N, 2 less than M, N is less than 10^5, indicating the length and width of the ball table.

Output format
Matches the number of batting lines described above.

Analysis

One’s face can not be done.

Although the forward solution is also a simulation, but it seems that many people still hang up, some write bfs, some write 700 + lines, I do not know what to write? Although julao has written 60 lines of simulation, it has used goto and so on.

But my dish, holding this question, began to draw pictures, drew 40 or 50 minutes, drew more than 10 rectangles, blind to find a rule, the result was 90 points, or good

After the exam, I got Julao’s help and found an upgraded version of the rules (I think the solution should add one: Find the rules!)

I started scribbling, and then I found out that it wasn’t right. I started at the end, and then I found a set of input 35, output 24 data, which happened to be the number of boundary points * 2 with two lines on the graph. So I tried even numbers and found a little different.

90Rule of division:

1.n=m 0species
2.nAnd m are even numbers ((n-2) + (m-2)) *2–> 2* (n+m) -8.
3.nAnd m are odd numbers (n+m) *4-8.
4.nAnd M odd odd even (n+m-2) *4 –> (n+m) *4-8

It’s through such a rectangle (I may draw more than 10 bars OVO) to find out.

 

That is, manually simulating BFS, counting from the terminal point.Oxblood redThe line is the first step.Pink lineThis is the second step.Yellow lineThis is the third step.Sky blueThe fourth step,Sea blue colorFifth steps

Continue to draw lines until there is no line to draw, you can see, except for four vertices, each point has two routes, must be able to walk to any one hole. So the number of points calculated (n-1+m-1) *2, then *2, is the number of routes, that is, (n+m) *4-8

However! This is just the case where N and m are mutually prime, and if they are not mutually prime, like 2 and 4, 6 and 3, they are not satisfied (you can draw them), so that’s why I started by dividing the odd and even (but because the drawing stops working, and I had to draw a matrix of 4 * 8, so I didn’t draw it.So deep law was not found.

How to solve this problem?

These two matrixes are 2*3 and 4*6, so you can see that the lines inside are identical. Just because the scale is enlarged, the line is even thinner. Because the lines are the same, the number of points that can reach the boundary is obviously the same, so in the case of non-isotropic, we just need to work outIt can be reduced to the smallest matrix of the number of routes can be.

The time complexity is reduced from O (N) to O (logN). The key is that the simulation is not easy to write, and the rules are easy to write.

I admit that my mind is very clear, and the data of 1E5 can think of rules.

#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    cin>>n>>m;
    cout<<(4*(n+m)/__gcd(n,m))-8;
    return 0;
}

 

Link of this Article: [NOIP simulation] slok

Leave a Reply

Your email address will not be published. Required fields are marked *