hdu 2841 Visible Trees(容斥原理)
来源：程序员人生 发布时间：2014-11-20 08:10:23 阅读次数：2760次
http://acm.hdu.edu.cn/showproblem.php?pid=2841
有1个n*m的方格，从(1,1)开始，每一个点有1棵树，1个人站在(0,0)点，问他能看到几棵树。当(0,0)和另外的点在1条直线上时他只能看到最近的1棵。
题目意在求在m*n的方格中有多少种y/x，由于两个y/x相等的点只能看到1个。有多少种y/x也就是有多少 个（x,y）x与y互质。其中(1<=x<=m,1<=n<=y)。
这样就上1题类似了，求1个区间[1,m]内与i的互质的数的个数。这里1<=i<=n，先求出与i不互质的，对i分解质因子然后容斥。
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
//#define LL long long
#define eps 1e⑼
#define PI acos(⑴.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;
LL ans;
int n,m;
int fac[maxn];
int prime[maxn];
int facCnt;
void getPrime()
{
bool flag[maxn];
memset(flag,false,sizeof(flag));
prime[0] = 0;
for(int i = 2; i < maxn; i++)
{
if(flag[i] == false)
prime[++prime[0]] = i;
for(int j = 1; j <= prime[0]&&i*prime[j]<maxn; j++)
{
flag[i*prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
void getFac(int num)
{
int tmp = num;
facCnt = 0;
for(int i = 1; i <= prime[0] && prime[i]*prime[i] <= tmp; i++)
{
if(tmp % prime[i] == 0)
{
fac[facCnt++] = prime[i];
while(tmp%prime[i] == 0)
tmp /= prime[i];
}
if(tmp == 1)
break;
}
if(tmp > 1)
fac[facCnt++] = tmp;
}
LL solve(int m)
{
//队列数组
int que[110];
int l = 0;
que[l++] = 1;
for(int i = 0; i < facCnt; i++)
{
int k = l;
for(int j = 0; j < k; j++)
que[l++] = fac[i]*que[j]*(⑴);
}
LL anw = 0;
for(int i = 0; i < l; i++)
anw += m/que[i];
return anw;
}
int main()
{
int test;
scanf("%d",&test);
getPrime();
for(int item = 1; item <= test; item++)
{
scanf("%d %d",&n,&m);
if(n > m)
swap(n,m);
ans = 0;
for(int i = 1; i <= n; i++)
{
getFac(i);
ans += solve(m);
}
printf("%I64d
",ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
