题意
给出了一个1001×1001的点阵，和查询q，你要求出从(0,0)点到(q,q)点有多少种不同的点到原点的斜率（也就是题目中所说的“可见”），原点到原点不算。
思路
很直接的就可以想到算出所有的点到原点的斜率，预处理出答案，我们的做法是：从原点开始，一圈一圈地向外扩张，对于每个点都计算一边斜率，然后确认该斜率是否出现过，没出现过的话，当前圈上的点到原点的不同的斜率个数+1，这样求出每一圈的数目，最后我们再求一个前缀和就好了。
时间很理想，是O(n^2*log(n))的，然而POJ上超时了。我拿到ideone上测速，是700ms，可以过的，可能是评测机不在状态吧ˊ_>ˋ。补救的方法就是打了个表，反正数据也很少。
然而这个题的精髓并不是这么水过去的，这个题其实是一个包装过了的法雷级数(Wikipedia::法里数列 可能需要科学上网)，如果试着一圈圈地写一下斜率，就会发现每一圈正好满足分子和分母互质的特性，每一圈的个数其实是欧拉函数值，整个答案是欧拉函数前缀和。所以我们就有了O(n)，的处理方法，详细的可以看这个题POJ 2478 Farey Sequence。
明明是刚做过的题居然都没有反应过来看来我真的是太迟钝了呢。
代码(暴力解法)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; struct Fac{ int up; int down; int gcd(int a,int b){ if (b == 0) { return a; } return gcd(b, a%b); } void reduce(){ int _gcd = gcd(up, down); up /= _gcd; down /= _gcd; } friend bool operator < (Fac a,Fac b){ if(a.up == b.up){ return a.down < b.down; }else return a.up < b.up; } }; Fac tg(int x,int y){ Fac ret; ret.up = y; ret.down = x; ret.reduce(); return ret; } set<Fac> vis; int ans[1001]; void get_ans(){ for (int i = 1; i <= 1000; i++) { int x = 0, y = i; for (x = 0; x <= i; x++) { Fac _tg = tg(x, y); if (!vis.count(_tg)) { vis.insert(_tg); ans[i]++; } } x = i; for (y = i-1; y >= 0; y--) { Fac _tg = tg(x, y); if (!vis.count(_tg)) { vis.insert(_tg); ans[i]++; } } ans[i] += ans[i-1]; } } int main(){ get_ans(); int caseCnt; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { int q; scanf(" %d",&q); printf("%d %d %d\n",d,q,ans[q]); } } |
