关键词：
题目大意：
一天，Vanya 来到了一片滑稽树林中，准备采摘滑稽果。滑稽树林可看作一个 n×n 的正方形，其中 m 个点上有滑稽果，某些点没有。（注意一个点上可能有多个滑稽果）
Vanya会沿向量 (dx,dy)(dx,dy) 方向移动。也就是说，如果Vanya在 (x,y) 处，她将移动到 ((x+dx) mod n,(y+dy) mod n)((x+dx) mod n,(y+dy) mod n) 处。每到一个点，她会拿走该点所有滑稽果。(dx,dy 为定值(输入中给出)，且 gcd(n,dx)=gcd(n,dy)=1)
由于滑稽树林太巨了，当Vanya走到一个她走到过的点时，她就会停止走动。
现在Vanya想知道她怎么走才能拿到最多的滑稽果。
（来自巨佬interestinLSY的翻译）
啊对了，n<= 10 ^ 5。
可见暴力不行呐
容易证明，(x, y)点在移动n次一定会回到原点，即每一条路线的移动周期是n。而且可以得出，在这个移动周期内，每一个点x, y 分别对n取模得到的值都不相同，也就是说，一条路线内每个点横纵坐标两两不相同。
那么我们只要求出每一个有果子的点属于哪一条路线就可以了。
首先可以随意选一条路线（为了方便，称为基线），将他的每一个点求出来，得到一个y已知时x的映射，而且上文已经说道，对于每一个0 <= y < n，都有唯一的x与之对应。
求出一条路线后，其他路线就可以由基线平移得到，所以对于每一个有果子的点，只要求出他和基线上y相同的点的距离，即第几条路线，然后开一个类似桶的数组记录每一条路线收获的果子数量，答案取max即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<stack> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 #define enter printf(" ") 13 #define space printf(" ") 14 #define Mem(a) memset(a, 0, sizeof(a)) 15 typedef long long ll; 16 typedef double db; 17 const int INF = 0x3f3f3f3f; 18 const db eps = 1e-8; 19 const int maxn = 1e6 + 5; 20 inline ll read() 21 22 ll ans = 0; 23 char ch = getchar(), last = ‘ ‘; 24 while(!isdigit(ch)) last = ch; ch = getchar(); 25 while(isdigit(ch)) 26 27 ans = ans * 10 + ch - ‘0‘; ch = getchar(); 28 29 if(last == ‘-‘) ans = -ans; 30 return ans; 31 32 inline void write(ll x) 33 34 if(x < 0) x = -x, putchar(‘-‘); 35 if(x >= 10) write(x / 10); 36 putchar(x % 10 + ‘0‘); 37 38 39 int n, m, dx, dy; 40 41 int a[maxn], b[maxn], ans = 0, pos; 42 int pnt[2][maxn]; 43 44 int main() 45 46 n = read(); m = read(); dx = read(); dy = read(); 47 for(register int i = 0, j = 1; j < n; i = (i + dy) % n, ++j) //求基线 48 a[(i + dy) % n] = (a[i] + dx) % n; 49 for(register int i = 1; i <= m; ++i) 50 51 int x = read(), y = read(), t; 52 t = (x - a[y] + n) % n; //算距离 53 b[t]++; 54 pnt[0][t] = x; pnt[1][t] = y; //第t条路线一定经过的点就是(x, y) 55 56 for(register int i = 0; i < n; ++i) 57 if(b[i] > ans) ans = b[i]; pos = i; 58 write(pnt[0][pos]); space; write(pnt[1][pos]); enter; 59 return 0; 60
492.构造矩形水题(代码片段)
https://leetcode-cn.com/problems/construct-the-rectangle/classSolutionpublic:vector<int>constructRectangle(intarea)intL=area,W=1;for(inti=1;i<=area/i;i++)if(area%i&# 查看详情
leetcode492构造矩形[数学枚举]heroding的leetcode之路(代码片段)
...走，不断寻找最接近的长宽，最好返回即可，代码如下：classSolutionpublic:vector<int>constructRecta 查看详情
leetcode492.构造矩形/638.大礼包/240.搜索二维矩阵ii(代码片段)
492.构造矩形2021.10.23每日一题题目描述作为一位web开发者，懂得怎样去规划一个页面的尺寸是很重要的。现给定一个具体的矩形页面面积，你的任务是设计一个长度为L和宽度为W且满足以下要求的矩形的页面。要求：... 查看详情
cf1435游记(代码片段)
目录CF1435游记AFindingSasuke题意简述解题思路参考代码BANewTechnique题意简述题目分析参考代码CPerformEasily题意简述题目分析参考代码DShurikens题意简述题目分析参考代码ESolomidOracle题意简述题目分析参考代码总结CF1435游记第一次AKdiv2，... 查看详情
cf每日一水(代码片段)
CF每日一水A.MadokaandMathDadtimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputMadokafinallyfoundtheadministratorpasswordforhercomputer.Herfatherisawell-knownpopula 查看详情
[cf930e]/[cf944g]coinsexhibition(代码片段)
[CF930E]/[CF944G]CoinsExhibition题目地址：CF930E/CF944G博客地址：[CF930E]/[CF944G]CoinsExhibition-skylee题目大意：一个长度为\(k(k\le10^9)\)的\(01\)串，给出\(n+m(n,m\le10^5)\)个约束条件，其中\(n\)条描述区间\([l_i,r_i]\)至少有一个\(0\)，其中\(m\)条描 查看详情
cf1017c(代码片段)
C.ThePhoneNumbertimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputMrs.Smithistryingtocontactherhusband,JohnSmith,butsheforgotthesecretphonenumber!TheonlythingM 查看详情
构造分组背包（cf）(代码片段)
IvanisastudentatBerlandStateUniversity(BSU).TherearendaysinBerlandweek,andeachofthesedaysIvanmighthavesomeclassesattheuniversity.TherearemworkinghoursduringeachBerlandday,andeachlessonattheuniversityl 查看详情
cf431bshowerline(代码片段)
Manystudentsliveinadormitory.Adormitoryisawholenewworldoffunnyamusementsandpossibilitiesbutitdoeshaveitsdrawbacks.Thereisonlyoneshowerandtherearemultiplestudentswhowishtohaveashowerinthemorning.That‘s 查看详情
cf985fisomorphicstrings(代码片段)
题目描述YouaregivenastringsssoflengthnnnconsistingoflowercaseEnglishletters.Fortwogivenstringssssandttt,saySSSisthesetofdistinctcharactersofsssandTTTisthesetofdistinctcharactersofttt.Thestringssssandtttar 查看详情
typescript键值，cf.ts(代码片段)
textdicituraaccettazione隐私cf7(代码片段)
text有用的cf命令(代码片段)
cf1368gshiftingdominoes(代码片段)
ShiftingDominoesBilllikestoplaywithdominoes.Hetookan(n imesm)boarddividedintoequalsquarecells,andcovereditwithdominoes.Eachdominocoverstwoadjacentcellsoftheboardeitherhorizontallyorvertically,andea 查看详情
cf546esoldierandtraveling(代码片段)
题目描述Inthecountrytherearennncitiesandmmmbidirectionalroadsbetweenthem.Eachcityhasanarmy.Armyoftheiii-thcityconsistsofaia_iai?soldiers.Nowsoldiersroam.Afterroamingeachsoldierhastoeitherstayinhiscityor 查看详情
cf1466ccaninepoetry(代码片段)
题目描述Afterhiswife'stragicdeath,Eurydice,Orpheusdescendedtotherealmofdeathtoseeher.Reachingitsgateswasuneasy,butpassingthroughthemprovedtobeevenmorechallenging.MostlybecauseofCerberus,thethree-heade 查看详情
cf1466ccaninepoetry(代码片段)
题目描述Afterhiswife'stragicdeath,Eurydice,Orpheusdescendedtotherealmofdeathtoseeher.Reachingitsgateswasuneasy,butpassingthroughthemprovedtobeevenmorechallenging.MostlybecauseofCerberus,thethree-heade 查看详情
cf580ckefaandparkdfs(代码片段)
Kefadecidedtocelebratehisfirstbigsalarybygoingtotherestaurant.Helivesbyanunusualpark.Theparkisarootedtreeconsistingofnverticeswiththerootatvertex1.Vertex1alsocontainsKefa‘shouse.Unfortunaelyforourhero 查看详情