神枪手JoneySun (Easy Version)

Time Limit: 1 s Memory Limit: 256 MB
Submission：146 AC：32 Score：100.00

Description
Easy Version 和 a little bit hard Version 只有数据范围的区别

JoneySun被邪恶的wifepie困在了一个由1×1的网格分割的监狱里，邪恶的wifepie为了看JoneySun的笑话，在监狱里的某处监视着JoneySun，幸运的是JoneySun手中有一把枪，不幸的是wifepie掌握了分身术。

我们认为这个监狱是一个2n×2m的网格，JoneySun被困在最中间，除了JoneySun所在处，网格其余的交点上都有一个wifepie的分身。JoneySun的枪射程是无限远，如果子弹射中分身，那么分身会消失，子弹继续沿直线行进。如果子弹射中wifepie本体，wifepie就会被JoneySun消灭。JoneySun想知道消灭wifepie最多需要多少子弹。

Input
第一行一个整数T(1≤T≤100)表示共有T组输入

第二行两个整数n,m(1≤n,m≤103)，含义见题面

Samples
input
1
1 1
output
8
Hint

如图所示，红点表示JoneySun所在位置，蓝点表示wifepie的分身，JoneySun最多需要8颗子弹就可以消灭wifipie所有的分身

请注意复杂度，T很大，请试试你能想到的所有玄学优化

题解：题目的意思就是求从源点发出的通向各个顶点的不重叠的射线有几条，即转化成求gcd(i,j)是否等于1，或者gcd(i,j)=d,gcd(i/d,j/d)是否等于1，如果等于1，即说明是一条可行的边，因为每一个矩形都是对称的，所以可以把它转化成一个象限的问题来求解。因为题目有100组的测试数据，复杂度较大，所以暴力求解会T，所以我们考虑用一个二维的前缀和进行预处理，然后O(1)进行查询。
AC代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<map>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<set>
#include<cctype>
#include<string>
#include<stdexcept>
#include<fstream>
#include<sstream>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 10000007
#define debug() puts("what the fuck!")
#define dedebug() puts("what the fuck!!!")
#define ll long long
#define ull unsigned long long
#define speed {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); };
using namespace std;
const double PI = acos(-1.0);
const int maxn = 1e6 + 50;
const int N = 35;
const int INF = 0x3f3f3f3f;
const int inf = 0xfffffff;//比INF小，防止累加爆int
const double esp_0 = 1e-6;
const double gold = (1 + sqrt(5)) / 2;
int gcd(int x, int y) {return y ? gcd(y, x % y) : x;
}
int n, m;
int dp[1020][1020];
int main() {mem(dp, 0);for (int i = 1; i <= 1010; ++i) {for (int j = 1; j <= 1010; ++j) {int step = gcd(i, j);if (step == 1)dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + step;//如果是可行边，则加上改点的值else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];//如果不是可行边，则不加}}}int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);int ans = dp[n][m] * 4 + 4;printf("%d\n", ans);}return 0;
}