E. Vanya and Field time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
Vanya decided to walk in the field of size n × n cells. The field contains m apple trees, the i-th apple tree is at the cell with coordinates(xi, yi). Vanya moves towards vector (dx, dy). That means that if Vanya is now at the cell (x, y), then in a second he will be at cell
. The following condition is satisfied for the vector:
, where
is the largest integer that divides both a and b. Vanya ends his path when he reaches the square he has already visited.
Vanya wonders, from what square of the field he should start his path to see as many apple trees as possible.
Input
The first line contains integers n, m, dx, dy(1 ≤ n ≤ 106, 1 ≤ m ≤ 105, 1 ≤ dx, dy ≤ n) — the size of the field, the number of apple trees and the vector of Vanya's movement. Next m lines contain integers xi, yi (0 ≤ xi, yi ≤ n - 1) — the coordinates of apples. One cell may contain multiple apple trees.
Output
Print two space-separated numbers — the coordinates of the cell from which you should start your path. If there are several answers you are allowed to print any of them.
Sample test(s) input
5 5 2 3
0 0
1 2
1 3
2 4
3 1 output
1 3 input
2 3 1 1
0 0
0 1
1 1 output
0 0 Note
In the first sample Vanya's path will look like: (1, 3) - (3, 1) - (0, 4) - (2, 2) - (4, 0) - (1, 3)
In the second sample: (0, 0) - (1, 1) - (0, 0)
好困╯﹏╰，不填坑了，睡覺去。有需要問思路的留言
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9;
const double eps = 1e-6;
const int N = 1000010;
int cas = 1;
struct _node{
int x,y,k;
void set(int _k, int _x, int _y)
{
k = _k;
x = _x;
y = _y;
}
};
_node point[N];
int xk[N],cnt[N];
int n,m,dx,dy;
void run()
{
point[0].set(0,0,0);
xk[0] = 0;
for(int i=1; i<n; i++)
{
point[i].set(i,(point[i-1].x+dx)%n,(point[i-1].y+dy)%n);
xk[point[i].x] = i;
}
memset(cnt,0,sizeof(cnt));
int x,y,k,y0,yk;
while(m--)
{
scanf("%d%d",&x,&y);
k = xk[x];
yk = point[k].y;
y0 = (y - yk + n) % n;
cnt[y0]++;
}
int mx=cnt[0], pos=0;
for(int i=1;i<n;i++)
if(mx < cnt[i])
mx=cnt[i], pos=i;
printf("0 %d\n",pos);
}
int main()
{
#ifdef LOCAL
freopen("case.txt","r",stdin);
#endif
while(scanf("%d%d%d%d",&n,&m,&dx,&dy)!=EOF)
run();
return 0;
} 思路：
題目的關鍵條件是這個
首先想個問題，先是一維的情況下，假設隻有一行的格子，長度為x，每次能移動的距離為dx，而且gcd(x,dx)=1，這樣手動模拟一下，可以發現規律，從某個點出發直到回到這個點上，步數均為x次，而且每次落下的點都是不重複的，也即這x次的位置覆寫了整條方格上的每一個方格。
那現在二維的情況下，gcd(n,dx) = gcd(n,dy) = 1，也就是從某一行和某一列的交點出發，要重新回到這個交點，就要經過n步而且這n步覆寫了每一行每一列。每個循環必須每個x走一次以及每個y走一次，n個格子屬于一組循環裡面的，總共有n*n個格子，是以有n組循環。一組循環内的格子是等價的。同一行内的n個格子均來自不同的n組。
現在考慮一組特殊的循環，這組循環從(0,0)開始出發
走了第一步以後就到 (dx%n, dy%n)
第二步到 (2*dx%n, 2*dy%n)
第k步到 (k*dx%n, k*dy%n)
用一個對應關系存儲，從（0，0）出發的，經過了k步以後，會到達位置（x[k] , y[k]）。
然後考慮普遍的情況了，每組循環都比如經過(0, y0)這個點
從這個點出發的第一步 (dx%n, (y0+dy)%n)
第k步到 (dx%n, (y0+dy)%n)， 也即(x[k], (y0+y[k])%n)
那麼現在給你某個坐标（x，y），要怎麼算出他屬于哪一組循環的呢
根據等式x[k]==x，可以求出對應的k的值
那就能求出對應的y[k]了，然後y0+y[k]==y → y0=y-y[k]
這樣就知道這個（x，y） 是屬于 （0，y0）這一組的了
那麼算法大概是這樣：
預處理出x[k],y[k]，時間複雜度o（n）
周遊每一個apple的坐标（x，y），求出對應的坐标（0，y0），然後cnt[y0]++，複雜度o（m）
找出值最大的cnt[y]，答案就是(0,y)了。 總複雜度o(n+m)
代碼如上。
轉載于:https://www.cnblogs.com/someblue/p/4136436.html