15ecjtu校赛1006 （dfs容斥）

Problem Description

在平面上有一个n*n的网格，即有n条平行于x轴的直线和n条平行于y轴的直线，形 成了n*n个交点(a,b)（1<=a<=n,1<=b<=n）。现在从(0,0)出发，问能形成多少条不同的射线，使其除了经过(0,0)还经过至少一个其他的交点。

Input

输入包含多组测试样例(40组左右)，处理到文件结束，每组测试包含一个数N(N <= 100000)

Output

每组数据输出射线的数目

Sample Input

2

3

Sample Output

3

7

类似HDU2841
此题拿容斥原理来做  注意是dfs方式处理的容斥 学习一下；

#include<bits/stdc++.h>

using namespace std;

int que[100010][20];

int jishu[100010];

void Init(){

    memset(jishu,0,sizeof(jishu));

    for(int i=2;i<=100000;i++)

    {

        if(jishu[i])

        continue;

        que[i][0]=i;

        jishu[i]=1;

        for(int j=2;j*i<=100000;j++)

         que[i*j][jishu[i*j]++]=i;

    }

}

__int64 dfs(int m,int n,int idx){

    __int64 ret=0;

    for(int i=idx;i<jishu[m];i++)

        ret+=n/que[m][i]-dfs(m,n/que[m][i],i+1);

    return ret;

}

int main()

{

    Init();

    int n;

    while(scanf("%d",&n)!=EOF)

{

        __int64 re=n;

        for(int i=2;i<=n;i++)

            re+=n-dfs(i,n,0);

        printf("%I64d\n",re);

    }

    return 0;

}