hdu2848 Visible Trees (容斥原理)

时间:2022-12-22 09:07:50

题意:

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

知识点:

容斥原理:(容许) 先不考虑重叠的情况,把包含于某条件中的所有对象的数目先计算出来,(排斥)然后再把计数时重复计算的数目排斥出去,使得计算的结果既无遗漏又无重复。

公式:hdu2848 Visible Trees (容斥原理)hdu2848 Visible Trees (容斥原理)          奇加偶减

一般求互质个数若用欧拉函数不好解决,则从反面考虑,用容斥。

模板:

void dfs(int c,int cur,int i,int j,LL ans1)      //dfs(c,1,i,0,1);
{
if(cur==c+1)
{
if(c&1)
ans-=ma/ans1;
else
ans+=ma/ans1;
return;
}
for(;j<cnt[i];j++)
{
dfs(c,cur+1,i,j+1,ans1*syz[i][j]);
}
}

题解:在同一条直线上的点的形式都是(ka,kb),这些点只能看到第一个。若gcd(a,b)==k’,(k’!=1),则其还能写成    (k’a’,k’b’)的形式。直到gcd(a,b)==1,(a,b)为第一个点。That is say,只要求出1~n与1~m中互质的数的个数,这题就OK了。一般求互质个数若用欧拉函数不好解决,则从反面考虑,用容斥。x为1~n中的一个数,x与1~m中互质的数的个数怎么求呢?用容斥,先找到有多少个数和x有1个公共的质因子,然后加上;再找到有多少个数与x有2个公共的质因子,然后减去;再找到有多少个数有多少个数与x有3个公共的质因子,然后加上……最后得到的个数,就是有多少个数与x不互质。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int ma,mi;
LL ans; int syz[N][7]; //素因子分解结果
int cnt[N];
void init() //筛选法求syz
{
memset(cnt,0,sizeof(cnt));
for(int i=2;i<N;i++)
{
if(cnt[i]==0)
{
for(int j=i;j<N;j+=i)
{
syz[j][cnt[j]++]=i;
}
}
}
} void dfs(int c,int cur,int i,int j,LL ans1) //dfs(c,1,i,0,1);
{
if(cur==c+1)
{
if(c&1)
ans-=ma/ans1;
else
ans+=ma/ans1;
return;
}
for(;j<cnt[i];j++)
{
dfs(c,cur+1,i,j+1,ans1*syz[i][j]);
}
} int main()
{
int t;
cin>>t;
init();
LL m,n;
while(t--)
{
scanf("%lld%lld",&m,&n);
ans=m*n;
ma=max(m,n),mi=min(m,n);
for(int i=2;i<=mi;i++)
{
for(int c=1;c<=cnt[i];c++)
{
dfs(c,1,i,0,1);
}
}
printf("%I64d\n",ans);
}
return 0;
} /*
100
23 54
56 54
44 54
10 10
100000 100000
*/

Visible Trees

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status

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

hdu2848 Visible Trees (容斥原理)的更多相关文章

  1. hdu 2841 Visible Trees 容斥原理

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

  2. HDU2841 Visible Trees &lpar;容斥原理&rpar;

    主题链接:http://acm.hdu.edu.cn/showproblem.php?pid=2841 题意: 一个人在(0,0)点,然后前面有一个m*n的格子 ,每一个格子的节点上有一棵树.问这个人 ...

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

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

  4. Visible Trees&lpar;hdu2841&rpar;

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

  5. HDU 2841 Visible Trees(数论)

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

  6. Visible Trees HDU - 2841

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

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

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

  8. 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 ...

  9. Visible Trees

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

随机推荐

  1. 推荐几个精致的web UI框架

    1.Aliceui Aliceui是支付宝的样式解决方案,是一套精选的基于 spm 生态圈的样式模块集合,是 Arale 的子集,也是一套模块化的样式命名和组织规范,是写 CSS 的更好方式. git ...

  2. ubuntu kylin中如何截图

    windows操作系统中,我通常使用的截图工具是QQ的“ctrl+alt+a”快捷键.但是在ubuntu中,linux qq常年不更新,我也就彻底放弃了使用了,反正ubuntu通常只是拿来开发.其实没 ...

  3. Sliverlight中PagedCollectionView的使用

    最近项目中一直在和PagedCollectionView这个类打交道.通过它,我们可以以分页的形式自动处理并显示集合中的片段,尤其是和Pager控件配合的时候更能彰显其威力. PagedColecti ...

  4. U盘做启动盘后,如何恢复原始容量

    上次用U盘装系统后,U盘缩水1G多,格式化和快速格式化,没有用,无法恢复U盘原来的容量,后来在网上查到一个方法,成功释放U盘空间,故将恢复方法写在下面. (1)右击“我的电脑”,选择“管理”选项,之后 ...

  5. 初步研究一下sourceTree

    今天研究sourceTree,在此小结一下 1.下载链接:https://www.atlassian.com/software/sourcetree 2.安装,注册账户登录,连接到GitHub账号上, ...

  6. 谈谈form-data请求格式

    最近一直都比较忙,坚持月月更新博客的计划不得中止了,今天好不容易抽出点时间来说说最近项目中遇到的一个问题,有关request post请求格式中的multipart/form-data格式. 引言 最 ...

  7. IdentityServer4-介绍大纲(译文)

    简介 IdentityServer4是一个基于ASP.NET CORE2使用OAuth2.0协议和OpenID Connect的框架 特性如下: Authentiaction作为一个Service 集 ...

  8. &lbrack;Swift&rsqb;LeetCode951&period; 翻转等价二叉树 &vert; Flip Equivalent Binary Trees

    For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left a ...

  9. mac出现zsh&colon; command not found&colon; ping解决方法

    Step1:终端输入以下命令: /sbin/ping 若出现如下信息,说明包含ping命令,是zsh的 PATH有问题,表示没有加载sbin下的命令,需要编辑.zshrc文件. Step2:终端打开. ...

  10. 11&period;14 Daily Scrum

    实现推荐菜谱时遇到问题,这个功能要和数据库和服务器有关,所以暂时放在一边,可能在beta版本实现. 部分成员已经完成基本任务,进行完善.   Today's Task Tomorrow's Task ...