HDU-2841 Visible Trees (莫比乌斯反演)

谁践踏了优雅 2022-06-10 13:53 196阅读 0赞

##                                      Visible Trees      ##

There are many trees forming a m \* n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.   
  
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

Input

The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

Output

For each test case output one line represents the number of trees Farmer Sherlock can see.

Sample Input

2
    1 1
    2 3

Sample Output

1
    5

## 题意：一个人站在(0,0)，从(1,1)开始到(m,n)有m\*n个树，以这个人为顶点作射线穿过树，问最多有多少条线，重叠的算一条。 ##

##     ##

## 思路：这题其实就是求gcd(x,y)=1(1<=x<=m,1<=y<=n)的x,y有多少对。这题可以用容斥去做，但是也可以用莫比乌斯反演轻松解决，这题可以说是莫比乌斯反演的入门题。http://blog.csdn.net/kele52he/article/details/77371745，这题也是莫比乌斯反演的入门题，和这题差不多，那题看懂了这题也就会了，唯一的区别就是(1,2)和(2,1)在这题里算两种，还省去了去重的麻烦。 ##

##     ##

## `#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <map> #include <algorithm> #include <set> #include <functional> using namespace std; typedef long long LL; typedef unsigned long long ULL; const int INF = 1e9 + 5; const int MAXN = 100005; const int MOD = 1000000007; const double eps = 1e-8; const double PI = acos(-1.0); bool vis[MAXN]; int primes[MAXN]; int miu[MAXN]; void calc(int limit) { memset(vis, false, sizeof(vis)); memset(miu, 0, sizeof(miu)); int tot = 0; miu[1] = 1; //根据定义，μ(1) = 1 for (int i = 2; i <= limit; i++) { if (!vis[i]) //未发现的质数 { primes[tot++] = i; miu[i] = -1; //质数，除了1以外，只有它自己是自己的质因数 //因此根据定义，μ(i) = (-1)^1 = -1 } for (int j = 0; j < tot; j++) { int k = i*primes[j]; if (k > limit)break; vis[k] = true; if (i % primes[j]) //i不是primes[j]的整数倍时，i*primes[j]就不会包含相同质因子。 miu[k] = -miu[i]; //此时根据其积性函数的特性得 miu[k] = miu[i]*miu[primes[j]]，因为primes[j]是质数，miu值为-1 else //然后化简得miu[k] = -miu[i]; (perfect!) break; } } } int main() { int T; int a, b; LL ans; scanf("%d", &T); calc(100003); while (T--) { ans = 0; scanf("%d%d", &a, &b); for (int i = 1; i <= min(a,b); i++) ans += (LL)miu[i] * (a / i)*(b / i); printf("%lld\n", ans); } }`         ##