程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 2841 Visible Trees(容斥原理)

hdu 2841 Visible Trees(容斥原理)

編輯：C++入門知識

hdu 2841 Visible Trees(容斥原理)

有一個n*m的方格，從(1,1)開始，每個點有一棵樹，一個人站在(0,0)點，問他能看到幾棵樹。當(0,0)和另外的點在一條直線上時他只能看到最近的一棵。

題目意在求在m*n的方格中有多少種y/x，因為兩個y/x相等的點只能看到一個。有多少種y/x也就是有多少個（x,y）x與y互質。其中(1<=x<=m,1<=n<=y)。

這樣就上一題類似了，求一個區間[1,m]內與i的互質的數的個數。這裡1<=i<=n，先求出與i不互質的，對i分解質因子然後容斥。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL __int64
//#define LL long long
#define eps 1e-9
#define PI acos(-1.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] 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]*(-1);
    }

    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;
}

上一頁:[leetcode]Valid Sudoku
下一頁:JDK5新特性之線程同步工具類（三）

C++入門知識

啦啦啦-根據關鍵字進行字符串拷貝，關鍵字字符串拷貝

啦啦啦-根據關鍵字進行字符串拷貝，關鍵字字符串拷貝實驗作業-

程序基石:C++多態的前提條件

程序基石:C++多態的前提條件准備知識C++中多態(p

圖解VC++工具欄和狀態欄編程實例

圖解VC++工具欄和狀態欄編程實例 demo工程 http:

[NOIP2009] 靶形數獨（搜索+剪枝），noip2009搜索剪枝

[NOIP2009] 靶形數獨（搜索+剪枝），noip200

zoj 3103 Cliff Climbing（spfa ）

zoj 3103 Cliff Climbing（spfa ）

歐幾裡得算法