HDU 2841 Visible Trees

      題意：就是給定一個坐標(n,m)，求(1,1)到(n,m)區間內x與y互質的坐標數。   思路：利用容斥從2到n，遍歷與m互質的個數。

 
#include <iostream>   
#include <cstdio>   
#include <cstdlib>   
#include <cmath>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <list>   
#include <deque>   
#include <queue>   
#include <iterator>   
#include <stack>   
#include <map>   
#include <set>   
#include <algorithm>   
#include <cctype>   
#include <cfloat>   
using namespace std;  
  
typedef __int64 LL;  
const int N=1000005;  
const LL II=1000000007;  
const int INF=0x3f3f3f3f;  
const double PI=acos(-1.0);  
  
LL n,m,pri[N];  
  
LL prime(LL x)  
{  
    LL i,j,numi=0;  
    for(i=2;i*i<=x;i++)  
        if(x%i==0)  
        {  
            pri[numi++]=i;  
            while(x%i==0)  
                x/=i;  
        }  
    if(x>1)  
        pri[numi++]=x;  
    return numi;  
}  
  
LL dfs(LL k,LL n)  
{  
    LL i,j,t,numi;  
    numi=prime(k);  
    LL sum=0;  
    for(i=1;i<(1<<numi);i++)  
    {  
        LL temp=1,k=0;  
        for(j=0;j<numi;j++)  
            if(i&(1<<j))  
            {   temp*=pri[j];   k++;    }  
        if(k&1) sum+=n/temp;  
        else    sum-=n/temp;  
    }  
    return n-sum;  
}  
  
int main()  
{  
    LL i,j,T;  
    scanf("%I64d",&T);  
    while(T--)  
    {  
        scanf("%I64d%I64d",&n,&m);  
        LL sum=m;  
        for(i=2;i<=n;i++)  
        {  
            sum+=dfs(i,m);  
        }  
        printf("%I64d\n",sum);  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cfloat>
using namespace std;

typedef __int64 LL;
const int N=1000005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL n,m,pri[N];

LL prime(LL x)
{
    LL i,j,numi=0;
    for(i=2;i*i<=x;i++)
        if(x%i==0)
        {
            pri[numi++]=i;
            while(x%i==0)
                x/=i;
        }
    if(x>1)
        pri[numi++]=x;
    return numi;
}

LL dfs(LL k,LL n)
{
    LL i,j,t,numi;
    numi=prime(k);
    LL sum=0;
    for(i=1;i<(1<<numi);i++)
    {
        LL temp=1,k=0;
        for(j=0;j<numi;j++)
            if(i&(1<<j))
            {   temp*=pri[j];   k++;    }
        if(k&1) sum+=n/temp;
        else    sum-=n/temp;
    }
    return n-sum;
}

int main()
{
    LL i,j,T;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&n,&m);
        LL sum=m;
        for(i=2;i<=n;i++)
        {
            sum+=dfs(i,m);
        }
        printf("%I64d\n",sum);
    }
    return 0;
}