Visible Trees HDU - 2841

时间:2022-09-01 14:14:25

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

在同一条直线(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 = , INF = 0x7fffffff;
int prime[maxn]; int get_cnt(int n, int m)
{
int ans = ;
for(int i = ; i * i <= n; i++)
{
if(n % i) continue;
while(n % i == ) n /= i;
prime[ans++] = i;
}
if(n != ) prime[ans++] = n;
int res = ;
for(int i = ; i < ( << ans); i++)
{
int tmp = , cnt2 = ;
for(int j = ; j < ans; j++)
{
if(((i >> j) & ) == ) continue;
tmp *= prime[j];
cnt2++;
}
if(cnt2 & ) 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 = ;
rap(i, , n)
{
sum += get_cnt(i, m);
} plld(sum);
} return ;
}

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

Visible Trees HDU - 2841的更多相关文章

  1. C - Visible Trees HDU - 2841 -莫比乌斯函数-容斥

    C - Visible Trees HDU - 2841 思路 :被挡住的那些点(x , y)肯定是 x 与 y不互质.能够由其他坐标的倍数表示,所以就转化成了求那些点 x,y互质 也就是在 1 - ...

  2. - Visible Trees HDU - 2841 容斥原理

    题意: 给你一个n*m的矩形,在1到m行,和1到n列上都有一棵树,问你站在(0,0)位置能看到多少棵树 题解: 用(x,y)表示某棵树的位置,那么只要x与y互质,那么这棵树就能被看到.不互质的话说明前 ...

  3. Visible Trees HDU - 2841(容斥)

    对于已经满足条件的(x1,y1),不满足条件的点就是(n*x1,n*y1),所以要求的就是满足点(x,y)的x,y互质,也就是gcd(x,y) == 1,然后就可以用之前多校的方法来做了 另f[i] ...

  4. HDU 2841 Visible Trees 数论&plus;容斥原理

    H - Visible Trees Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u S ...

  5. HDU 2841 Visible Trees(容斥定理)

    Visible Trees Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) To ...

  6. HDU 2841 Visible Trees(数论)

    标题效果:给你个m*n方格,广场格从(1,1)开始. 在树中的每个点,然后让你(0,0)点往下看,问:你能看到几棵树. 解题思路:假设你的视线被后面的树和挡住的话以后在这条线上的树你是都看不见的啊.挡 ...

  7. hdu 2841 Visible Trees 容斥原理

    Visible Trees Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Pr ...

  8. hdu2848 Visible Trees &lpar;容斥原理&rpar;

    题意: 给n*m个点(1 ≤ m, n ≤ 1e5),左下角的点为(1,1),右上角的点(n,m),一个人站在(0,0)看这些点.在一条直线上,只能看到最前面的一个点,后面的被档住看不到,求这个人能看 ...

  9. Hdu2841 Visible Trees 2017-06-27 22&colon;13 24人阅读 评论&lpar;0&rpar; 收藏

    Visible Trees Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) To ...

随机推荐

  1. 恋爱虽易,相处不易:当EntityFramework爱上AutoMapper

    剧情开始 为何相爱? 相处的问题? 女人的伟大? 剧情收尾? 有时候相识即是一种缘分,相爱也不需要太多的理由,一个眼神足矣,当EntityFramework遇上AutoMapper,就是如此,恋爱虽易 ...

  2. HDU 1452 &lpar;约数和&plus;乘法逆元&rpar;

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1452 题目大意:求2004^X所有约数和,结果mod 29. 解题思路: ①整数唯一分解定理: 一个 ...

  3. Log4J简单使用

    一.一般会将commons-logging和Log4j一起使用   原因:1.commons-logging功能较弱 2.log4j功能强大. 所需jar:       log4j-1.2.16.ja ...

  4. as3中的多线程

    从fp11.4开始支持worker技术, 即as3中的线程概念, 到了fp11.5, flascc中开始支持pthread家族来创建线程. 总的来说, as3中有两种创建线程的方法: 1.直接在as3 ...

  5. &lbrack;置顶&rsqb; 文件io(一)--unix环境高级编程读书笔记

    unix-like(后面以linux为例)系统中的文件操作只需要五个函数就足够了,open.close.read.write以及lseek.这些操作被称为不带缓存的io,这里有必要说一下带缓存和不带缓 ...

  6. gridview中使用href调用javascript

    传递参数(多个)可用以下两种方法: 方法一: <asp:TemplateField HeaderText="列名1"> <ItemTemplate> &lt ...

  7. DOM备忘录

    nodeName和nodeValue属性 对于element节点而言,nodeName是标签名,nodeValue是null:而对于textNode节点而言,nodeName是#Text,nodeVl ...

  8. yum 安装 python-pip 失败解决方法

    这个包在EPEL源里,要添加EPEL源才可以.然后按博客里说的方法添加,执行以下命令: sudo rpm -ivh epel-release* 第一种方式:由于epel在禁用列表里需要另外加参数yum ...

  9. shell的exec命令

    工作中遇到运维人员挂supervisor的时候建议启动使用命令control.sh start, 并且在control.sh 里面启动命令: exec -c ./bin/xxx -f config/x ...

  10. pytorch解决鸢尾花分类

    半年前用numpy写了个鸢尾花分类200行..每一步计算都是手写的  python构建bp神经网络_鸢尾花分类 现在用pytorch简单写一遍,pytorch语法解释请看上一篇pytorch搭建简单网 ...