Visible Trees HDU - 2841

时间：2019-01-25 19:40:39 阅读：164 评论：0 收藏：0 [点我收藏+]

Visible Trees

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4331 Accepted Submission(s): 1991

Problem Description

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

Source

2009 Multi-University Training Contest 3 - Host by WHU

在同一条直线（y = kx （k为自然数））上的点只能看见最前面的最前面的点的 y 和 x 肯定互质

所以就变成了求m * n 这个区域中互质的 x 与 y 的对数

对于每一个1 ~ n 求 1 ~ m中有多少个与之互质的数加起来就好了

tip：容斥求出与之有公因子的数然后m - 这个数就是与之互质的数的个数了

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 10010, INF = 0x7fffffff;
int prime[maxn];

int get_cnt(int n, int m)
{
    int ans = 0;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i) continue;
        while(n % i == 0) n /= i;
        prime[ans++] = i;
    }
    if(n != 1) prime[ans++] = n;
    int res = 0;
    for(int i = 1; i < (1 << ans); i++)
    {
        int tmp = 1, cnt2 = 0;
        for(int j = 0; j < ans; j++)
        {
            if(((i >> j) & 1) == 0) continue;
            tmp *= prime[j];
            cnt2++;
        }
        if(cnt2 & 1) res += m / tmp;
        else res -= m / tmp;
    }
    return m - res;
}

int main()
{
    int n, m, t;
    rd(t);
    while(t--)
    {
        rd(n), rd(m);
        LL sum = 0;
        rap(i, 1, n)
        {
            sum += get_cnt(i, m);
        }

        plld(sum);
    }

    return 0;
}