hdu 2841 Visible Trees(容斥原理)
來源：程序員人生 發布時間：2014-11-20 08:10:23 閱讀次數：2880次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
